摘要:

AbstractBroadcasting is an information dissemination problem in which information originating at one node of a communication network (modeled as a graph) must be transmitted to all other nodes as quickly as possible. A broadcast graph is a graph which permits broadcasting from any originator in minimum time. in this paper, we present new methods for constructing sparse broadcast graphs. Our constructions are based on graph compounding operations which are relative to vertex sets with certain properties that depend on the broadcast protocols of the graphs. We show that many previous methods for constructing sparse broadcast graphs are special cases of our methods. We demonstrate our constructions by producing new sparse broadcast graphs and by showing how many previously constructed graphs can be obtained in a systematic way.

ISSN:0028-3045    

DOI:10.1002/net.3230260302

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractFor given nonnegative integerskandD, we consider the problem of determiningn0(k, D), The smallest numbernfor which there exists ak‐regular bipartite graph onnvertices with diameterD. We solve the problem for all pairs(k, D) withD≢ 2 (mod 4) andD≢ 3 (mod 4), for all pairs (k,D) withkeven orkprime andD≢ 3 (mod 4), for all pairs withD≤ 9 ork≤ 4, and for a few other pairs. in the remaining cases, we obtain lower and upper bounds f

ISSN:0028-3045    

DOI:10.1002/net.3230260303

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractA cycleCin a graphGis aHamilton cycleifCcontains every vertex ofG. Similarly, a pathPinGis aHamilton pathifPcontains every vertex ofG. We say thatGisHamilton‐connectedif for any pair of vertices,uandvofG, There exists a Hamilton path fromutov. IfGis a bipartite graph with bipartition sets of equal size, and there is a Hamilton path from any vertex in one bipartition set to any vertex in the other, The nGis said to beHamilton‐laceable. We present a proof showing that then‐dimensionalk‐ary butterfly graph, denoted BF(k,n), contains a Hamilton cycle. Then, we use this result in proving the stronger result thatBF(k,n) is Hamilton‐laceable whennis even and Hamilton‐connected for odd

ISSN:0028-3045    

DOI:10.1002/net.3230260304

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractThis paper describes a new approach to finding solutions to the optimal communication spanning tree problem (OCSTP) using a genetic algorithm. The difficulties posed by this problem are reviewed and a genetic algorithm that consistently finds very good, if not optimal, solutions to it is presented. Finally, a comparison of the genetic algorithm's solutions to those produced by a good heuristic is given that demonstrates the genetic algorithm's ability to find solutions at least equivalent to, if not superior to, those found by the heuristic.

ISSN:0028-3045    

DOI:10.1002/net.3230260305

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230260301

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY