Journal of Interconnection Networks

Broadcasting is an information dissemination problem in a connected network in which one node, called the originator, must distribute a message to all other nodes by placing a series of calls along the communication lines of the network. In every unit of time, the informed nodes aid the originator in distributing the message. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for certain graphs like trees, unicyclic graphs, tree of cycles, necklace graphs, fully connected trees and tree of cliques. In this paper we study the broadcast problem in k-path graphs. For any originator of the k-path graph we present a (4 – ϵ)-approximation algorithm in the worst case. The algorithm gives a better approximation ratio for some large classes of k-path graphs. Moreover, our algorithm generates the optimal broadcast time for some cases.

Let F be an edge subset and F′ a subset of vertices and edges of a graph G. If G − F and G − F′ have no fractional perfect matchings, then F is a fractional matching preclusion (FMP) set and F′ is a fractional strong matching preclusion (FSMP) set of G. The FMP (FSMP) number of G is the minimum size of FMP (FSMP) sets of G. In this paper, we study the fractional matching preclusion number and the fractional strong matching preclusion number for the Möbius cube MQ_n. In adddition, all the optimal fractional strong preclusion sets of these graphs are categorized.

In this paper, we provide an algorithm for traversing geometric graphs which visits all vertices and reports every vertex and edge exactly once. To achieve this, we combine a given geometric graph G with the integer lattice, seen as a graph, in such a way that the resulting hypothetical graph can be traversed using a known algorithm which is based on face routing. To overcome the problem with hypothetical vertices and edges, we develop an algorithm for visiting any k-th neighborhood of a vertex in a graph straight-line drawn in the plane using O(k log k) memory. The memory needed to complete the traversal of a geometric graph then turns out to depend on the maximum graph distance among pairs of distinct vertices of G whose Euclidean distance is greater than one and less than $2\sqrt{2}$.

In this paper, we propose a method to organize a tree-based Peer-to-Peer (P2P) overlay for video streaming which is resilient to the temporal reduction of the upload capacity of a node. The basic idea of the proposed method is: (1) to introduce the redundancy to a given tree-structured overlay, in such a way that a part of the upload capacity of each node is proactively used for connecting to a sibling node, and (2) to use those links connecting to the siblings to forward video stream to the siblings. More specifically, we prove that even if the maximum number of children of a node temporally reduces from m to m − k for some 1 ≤ k ≤ m − 1, the proposed method continues the forwarding of video stream to all of m children in at most 2^x hops, where x is the smallest integer satisfying m − k ≥ m/2^x. We also derive a sufficient condition to bound the increase of the latency by an additive constant. The derived sufficient condition indicates that if each node can have at least six children in the overlay, the proposed method increases the latency by at most one, provided that the number of nodes in the overlay is at most 9331; namely the proposed method guarantees the delivery of video stream with a nearly optimal latency.

This paper considers the problem of improving the routing performance of hierarchical Delaunay networks. Delaunay network is a network topology for peer-to-peer systems based on the Delaunay triangulation of a set of points associated with a set of peers. It is known that Delaunay networks have a favorable property as a topology for peer-to-peer systems such that a greedy routing scheme always delivers a given message to its destination without encountering a dead-end. The key idea used in the proposed method is to apply a hash function to the address of participant peers. More concretely, by applying a hash function to the coordinate point of the peers and by associating several points to each peer, we could realize an overlay so that the number of hops to the destination in the original network could be significantly reduced.