Broadcasting is one of the fundamental information dissemination primitives in interconnection networks, where a message is passed from one node (called originator) to all other nodes in the network. Following the increasing interest in interconnection networks, extensive research was dedicated to broadcasting. Two main research goals of this area are finding inexpensive network structures that maintain efficient broadcasting and finding the broadcast time for well-known and widely used network topologies. In the scope of this study, we will mainly focus on determining the broadcast time and nearoptimal broadcasting schemes in networks. Determination of the broadcast time of any node in an arbitrary network is known to be NP-hard. Polynomial time solutions are known only for a few network topologies. There also exist various heuristic and approximation algorithms for different network topologies. In this study, we consider the broadcast time problem on graphs that comprise some recursive structures. We initiate a novel direction to designing broadcasting algorithms on recursively defined graphs. We provide a theoretical foundation for future broadcasting studies, as well as discuss several practical applications of the approach we introduce.

We study temporal analogues of the Unrestricted Vertex Separator problem from the static world. An $(s,z)$-temporal separator is a set of vertices whose removal disconnects vertex $s$ from vertex $z$ for every time step in a temporal graph. The $(s,z)$-Temporal Separator problem asks to find the minimum size of an $(s,z)$-temporal separator for the given temporal graph. We introduce a generalization of this problem called the $(s,z,t)$-Temporal Separator problem, where the goal is to find a smallest subset of vertices whose removal eliminates all temporal paths from $s$ to $z$ which take less than $t$ time steps. Let $τ$ denote the number of time steps over which the temporal graph is defined (we consider discrete time steps). We characterize the set of parameters $τ$ and $t$ when the problem is $\mathcal{NP}$-hard and when it is polynomial time solvable. Then we present a $τ$-approximation algorithm for the $(s,z)$-Temporal Separator problem and convert it to a $τ^2$-approximation algorithm for the $(s,z,t)$-Temporal Separator problem. We also present an inapproximability lower bound of $Ω(\ln(n) + \ln(τ))$ for the $(s,z,t)$-Temporal Separator problem assuming that $\mathcal{NP}\not\subset\mbox{\sc Dtime}(n^{\log\log n})$. Then we consider three special families of graphs: (1) graphs of branchwidth at most $2$, (2) graphs $G$ such that the removal of $s$ and $z$ leaves a tree, and (3) graphs of bounded pathwidth. We present polynomial-time algorithms to find a minimum $(s,z,t)$-temporal separator for (1) and (2). As for (3), we show a polynomial-time reduction from the Discrete Segment Covering problem with bounded-length segments to the $(s,z,t)$-Temporal Separator problem where the temporal graph has bounded pathwidth.

Broadcasting is an information dissemination problem in a connected graph in which one vertex, called the originator, must distribute a message to all other vertices by placing a series of calls along the edges of the graph. Every time the informed vertices aid the originator in distributing the message. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. We designed an efficient heuristic, which improves the results of existing heuristics in most cases. Extensive simulations show that our new heuristic outperforms the existing ones for most of the commonly used interconnection networks in some network models generated by network simulator ns-2.

Recent years have witnessed the rapid growth of social network services. Real-world social networks are huge and changing over time. Consequently, the problems in this area have become more complex. Community detection is one of the most important problems in social networks. A good community can be defined as a group of nodes that are highly connected to each other and loosely connected to the nodes outside the community. Regarding the fact that social networks are huge in size, having complete information of the whole network is almost impossible. As a result, the problem of local community detection has become more popular in recent years. The problem of community detection in dynamic networks is well-investigated however, the local community detection is not widely addressed by researchers. In this paper, this problem is investigated by employing a number of existing local community detection algorithms in a dynamic structure. Results are reported in two different experiments. Experimental results show that one of the algorithms (algorithm P) outperforms other algorithms regarding the employed dynamic structure. The results indicate that algorithm P is much faster than other local community detection algorithms in dynamic networks.

We study the dominating set problem in an online setting. An algorithm is required to guarantee competitiveness against an adversary that reveals the input graph one node at a time. When a node is revealed, the algorithm learns about the entire neighborhood of the node (including those nodes that have not yet been revealed). Furthermore, the adversary is required to keep the revealed portion of the graph connected at all times. We present an algorithm that achieves 2-competitiveness on trees. We also present algorithms that achieve 2.5-competitiveness on cactus graphs, (t-1)-competitiveness on K_{1,t}-free graphs, and Θ(√{Δ}) for maximum degree Δ graphs. We show that all of those competitive ratios are tight. Then, we study several more general classes of graphs, such as threshold, bipartite planar, and series-parallel graphs, and show that they do not admit competitive algorithms (i.e., when competitive ratio is independent of the input size). Previously, the dominating set problem was considered in a different input model (often together with the restriction of the input graph being always connected), where a vertex is revealed alongside its restricted neighborhood: those neighbors that are among already revealed vertices. Thus, conceptually, our results quantify the value of knowing the entire neighborhood at the time a vertex is revealed as compared to the restricted neighborhood. For instance, it was known in the restricted neighborhood model that 3-competitiveness is optimal for trees, whereas knowing the neighbors allows us to improve it to 2-competitiveness.

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Once informed, the nodes aid the originator in distributing the message. Finding the broadcast time of a vertex in an arbitrary graph is NP-complete. The problem remains NP-complete even for 3-regular planar graphs and for graphs whose vertex set can be partitioned into a clique and an independent. Several approximation and heuristics algorithms have been presented in the literature. The problem is solved polynomially only for fully connected trees and some tree-like graphs, where two cycles do not intersect. In this paper, we study the broadcast problem in Cactus Graphs in which any two simple cycles have at most one vertex in common. The problem is proved to be NP-complete in general Cactus Graphs. In this paper we provide a heuristic algorithm to find the broadcast time in k-restricted Cactus graphs called a k-cycle graph. Intensive simulations showed that the heuristic generates the optimal broadcast time in most of the k-cycle graphs.

Multicast communication constrained by end-to-end delay and inter-destination delay variation is known as Delay and Delay Variation Bounded Multicast (DVBM). In this paper, we propose a dynamic multi-core multicast approach to solve the DVBM problem. The proposed three-phase algorithm, Multi-core DVBM Trees (MCDVBMT), semi-matches group members to core nodes. The message is disseminated to group members using trees rooted at the designated core nodes. MCDVBMT dynamically reorganizes the rooted trees in response to changes to multicast group members. On average, only 5.2% of the total requests trigger re-executions and 53.6% of the graphs generated by MCDVBMT suffer from re-execution before receiving all dynamic requests.

In this paper, we present a new heuristic that generates broadcast schemes in arbitrary networks. The heuristic gives optimal broadcast time for HyperCube, and best results for Cube-Connected Cycles and large Shuffle-Exchange graphs. Extensive simulations show that our new heuristic outperforms the best known broadcast algorithms for two different network models representing Internet generated using BRITE (Boston university Representative Internet Topology gEnerator). It also has a low time complexity, O(\E\log\V\), which is lower compared to the complexities of most of the other good algorithms. The last advantage of the heuristic is that approximately one half of the nodes are informed via a shortest path from the originator, while the rest of the vertices receive the message via a path at most three hops longer.

With the increasing popularity of multicomputers, efficient way of communication within its processors is a popular area of research. Multicomputers refer to a computer system that has multiple processors, they have high computational power and they can perform multiple tasks concurrently. Mesh and Torus are some of the commonly used network topologies in building multicomputer systems. Their performance highly depends on the underlying network communication such as multicast. Multicast is a communication method in which a message is sent from a source node to a certain number of destinations. Two major parameters used to evaluate multicast are time that a multicast process takes to deliver the message to all destinations and traffic that indicates the number of links used for this process. Research indicates that in general, it is NP-complete to find an optimal multicasting algorithm which is efficient on both time and traffic. This paper suggests two new algorithms to achieve multicast in mesh and torus networks. Extensive simulations of these algorithms show that in practice they perform better than existing ones.

We study nonadaptive broadcasting in trees, a process of sending a message from one vertex in a tree to all other vertices. In the nonadaptive model, each vertex has a specified, ordered list of its neighbors. After receiving a broadcast message, a vertex sends the message to its neighbors, one after another, in the order specified by the list. The broadcast is completed when all vertices have received the message. We obtain lower and upper bounds on the minimum time required to complete a nonadaptive broadcast in a tree and improved upper bounds for general graphs. We give a polynomial time algorithm for determining the minimum nonadaptive broadcast time of any given tree. We also show how to construct the largest possible trees having a given nonadaptive broadcast time. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 157–168 2011

In this paper, we present a new heuristic that generates broadcast schemes in arbitrary networks. The heuristic gives optimal broadcast time for ring, tree and grid if the originator is on the corner. Extensive simulations show that our new heuristic outperforms the best known broadcast algorithms for two different network models representing Internet and ATM networks. It also allows to generate broadcast time of networks of bigger size because its time complexity, O(|E|), is lower compared to the complexities of the other algorithms. The last advantage of the heuristic is that every node is informed via a shortest path from the originator.

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Once informed, the nodes aid the originator in distributing the message. Finding the minimum broadcast time of a vertex in an arbitrary graph is NP-complete. The problem is solved polynomially only for trees, unicyclic graphs, and tree of cycles. In this paper we consider broadcasting in a new class called the Fully Connected Trees (FCT). We present a O(n log n) algorithm to find the broadcast time of any originator in an arbitrary FCT.

Abstract The term k‐broadcast indicates the process of disseminating a message from one vertex to all vertices of a graph in such a way that in each time unit, an informed vertex can send the message to up to k of its neighbors. The k‐broadcast center of a graph is the set of vertices that can initiate a minimum time k‐broadcast within the graph. We present a linear algorithm to determine the k‐broadcast center of a given tree. From this, we obtain a linear time algorithm for finding the k‐broadcast time of any vertex of the tree and, thus, the k‐broadcast time of the tree itself. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Triple loop networks (graphs) are generalizations of the ring topology where every vertex v is linked to 6 vertices v a, v b, v c. In this paper, we study the broadcast problem in optimal triple loop graphs. In 1987 for a restricted case a = -(b + c) the (maximum) number of vertices in the sub- optimal Triple loop graph has been proved to be a quadratic function of diameter d. In 1998 the broadcast time of this graph is proved to be d + 3. Recently, in 2003 the Optimal Triple Loop Graph in general was constructed, where its number of vertices is a cubic function of d. In this paper we prove d + 2 lower bound and d + 5 upper bound for broadcasting in general Optimal Triple Loop Graph. We also generalize our upper bound algorithm in Multiple Loop Graphs giving d + 2 k-1 general upper bound where the degree of every vertex is 2 k.

In this paper the problem of broadcasting in networks with weighted nodes is considered. This model is defined on networks in which nodes are assigned some weights representing the internal process or delay that they should perform before sending data to their neighboring nodes. This model has real world applications in parallel computation and satellite terrestrial networks. The problem is shown to be NP-complete. In this paper we present three algorithms to find near optimal broadcast time of an arbitrary network with weighted nodes. We also present our simulation results to compare the performance of these algorithms.

In this paper a new model for information dissemination in communication network is presented. The model is defined on networks in which nodes are assigned some weights representing the internal delay they should pass before sending data to their neighbors. The new model, called weighted-vertex model, comes to have real world applications in parallel computation and satellite terrestrial networks. As a generalization of the classical model, optimum broadcasting in weighted-vertex model is NP_Hard. The problem remains NP_Hard in some classes of weighed-vertex graphs. We show existence of approximation algorithms for the broadcasting problem in weighted vertex model, as well as better approximations for specific subclasses of weighted graphs.

Broadcast algorithms are are very important in parallel and distributed computing. In this paper we design new sparce graphs and present a minimum time broadcast algorithms from any vertex of these graphs. A broadcast graph on n vertices is a graph which allows any vertex to broadcast in time [log n]. A minimum broadcast graph on n vertices is a broadcast graph with the minimum number of edges over all broadcast graphs on n vertices. This minimum number of edges is denoted by B(n). Many papers have presented methods to construct broadcast graphs. Here we present a method to construct a broadcast graph on n + 1 vertices by adding a vertex to a broadcast graph on n vertices. Our general upper bound on B(n) improves the best known upper bounds for almost all odd values of n. Our broadcast algorithms are simple. Our new broadcast graphs can be combined using some of the known methods to obtain further improvements.

Survivable network design has become increasingly important due to the need for reliable communication service. Its main purpose is to provide cost-efficient spare capacity reservation at certain survivability level. In this paper, we introduce two pre-planned path restoration algorithms for spare capacity design in mesh-like networks. First one is a spanning tree based algorithm, which needs less spare capacity than the well known hierarchical tree algorithm while keeping the same level of restorability. The second algorithm is a cycle based tree algorithm with backup parents and extra cycle edges, which forms cycles with the original spanning tree edges. Simulation results show that this algorithm works much better than the other two algorithms on restorability. Both algorithms have time complexity O(n3) and space complexity O(n2), where n is the total number of nodes in the network.

Abstract The Knödel graphs Wd,n are regular graphs, of even order n and degree d ≤ ⌊log n⌋. They have been introduced by W. Knödel as gossip graphs for d = ⌊log n⌋. A logarithmic algorithm for the minimum path problem in Knödel graphs is an open problem despite the fact that they are bipartite and highly symmetric. In this paper, we describe a logarithmic time two‐approximation algorithm for the shortest path in the Knödel graph on 2d vertices with degree d. We also prove that for a subset of the set of vertices, the algorithm gives a minimum length path. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 86–91 2007

Double loop graphs are extensions of the ring topology which are obtained by regularly adding 2 extra edges per vertex. An optimal graph of diameter d has the maximum possible number of vertices. The optimal structure of double loop graphs, as well as the broadcast time and an optimal broadcast scheme are known. In this paper, we define the family of bipartite double loop graphs (BDLG) G = (V, E) where V = V0cup V1, V0cap V1= phi and |V0| = |V1|. We show that the maximum number of vertices that a BDLG of diameter d can have is 2d2. We also study the broadcast problem and find that the broadcast time is d + 2. Finally we present an optimal broadcast scheme for these bipartite double loop graphs

Performance of multicomputers largely depends on that of the underlying network communications such as multicast. Two major parameters used to evaluate multicast routing are the time it takes to deliver the message to all destinations and the traffic which refers to the total number of links involved. Mesh is a network topology widely used in multicomputers. It has been proved that, in mesh network, it is NP-hard to find the multicast routing which is optimal on both time and traffic. In this paper, we proposed two efficient multicast algorithms designed for store-and-forward switched mesh-connected multicomputers: DIAG and DDS. They are both tree-based shortest path multicast algorithms whose complexity is O(KN) or less. Performance evaluations of these algorithms resulted from simulations are given at the end.

In this paper, we introduce a new concept in fault-tolerance, namely the global fault-tolerance of interconnection networks. We pose the problem of characterizing the fault-tolerance of an interconnection network, modelled as an undirected unweighted graph, by a scalar, in a global manner. This can be achieved by defining an adequate metric. In this paper, we propose such a metric and we apply it on two comparative analysis: for three infinite families of minimum broadcast graphs (hypercubes, recursive circulants, and Knodel graphs), and for five families of hypercubic graphs (butterfly, wrapped butterfly, shuffle exchange, de Bruijn, and cube connected cycles)

Abstract Multiple message broadcasting is the process of multiple message dissemination in a communication network in whichmmessages, originated by one vertex, are transmitted to all vertices of the network. A graphGwithnvertices is called a m‐message broadcast graph if its broadcast time is the theoretical minimum.Bm(n) is the minimum number of edges in any m‐message broadcast graph onnvertices. An m‐message minimum broadcast graph is a broadcast graphGonnvertices havingBm(n) edges. This article presents several lower and upper bounds onBm(n). In particular, it is shown that modified Knödel graphs are m‐message broadcast graphs form≤ min⌊logn⌋,n− 2⌊logn⌋. From the Cartesian product of some broadcast graphs we obtain better upper bounds onBm(n), and in some cases we can prove thatBm(n) =O(n). The exact value ofB2(2k) is also established. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 218–224 2006

Broadcasting is the problem of dissemination of information in which one piece of information needs to be transmitted to a group of individuals connected by an interconnection network. A widely accepted communication model for this problem is the 1-port, constant model, in which a node of the network can transmit the message only to one neighbor at a time, and the transmission time is constant, regardless the length of the message. Finding an optimum strategy for broadcasting under this model, such that this process is accomplished in minimum time, has been proved to be NP-complete for an arbitrary network. If we model the interconnection network as an undirected graph, the minimum broadcast time function associates to each vertex an integer which represents the minimum time necessary to broadcast the information stored in that vertex to all other vertices. The values of the minimum broadcast time function are known for a very restricted class of graphs, mainly regular ones, and very little is known about this function in general. In this paper we explore two new properties of this function. The first property establishes a connection between this function and the behavior of the optimal broadcast schemes. We prove an exact result for trees and we conjecture it for arbitrary graphs. The second property establishes a connection between this function and the density of the graph.

We describe an ordering of the vertices of a 2-dimensional torus and study the upper bound on the orderly broadcast time. Along with messy broadcasting, orderly broadcasting is another model where the nodes of the network have limited knowledge about their local neighborhood. However, while messy broadcasting explores the worst-case performance of broadcast schemes, orderly broadcasting, like the classical broadcast model, is concerned with finding a fixed ordering of the vertices of a graph that will minimize the overall broadcast time.

We present a heuristic algorithm for k-broadcasting in an arbitrary network. This heuristic generates optimal k-broadcast time in grid graph when k/spl ges/2. In two-dimensional torus graph, it also generates optimal k-broadcast time when k/spl ges/3, while giving a bound of /spl lfloor/m/2/spl rfloor/+/spl lfloor/n/2/spl rfloor/+1 when k=2, where m and n are the number of rows and columns in the graph. In practice, the new heuristic outperforms best known 1-broadcast algorithm for three different network design models. The new algorithm runs fast. The time complexity of the algorithm is O(R /spl middot/ m), where R represents the rounds of broadcasting, and m stands for the total number of edges in the graph.

Abstract We continue the investigation of k‐broadcasting, a variant of broadcasting in which an informed vertex can call up to k of its neighbors in each time unit. We focus on k‐broadcasting in trees. In particular, we asymptotically determine the maximum number of vertices in any tree with given k‐broadcast time and describe the structure of the trees that achieve this maximum. © 2001 John Wiley & Sons, Inc.

We continue the investigation of k-broadcasting, a variant of broadcasting in which an informed vertex can call up to k of its neighbors in each time unit. A focus of the investigation into broadcasting is the function Bk(n), which is the minimum number of edges in any n vertex graph such that each vertex can originate a k-broadcast that completes in minimum time. We give several methods to construct graphs which allow minimum-time k-broadcasting from each vertex. These constructions give improvements to the best current upper bounds on Bk(n). We also give an improvement to the best existing lower bound on Bk(n). In addition, a few new exact values of Bk(n) are determined. © 2001 John Wiley & Sons, Inc.