Paper Info
Title
New Construction of Broardcast Graphs
Abstract
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 dlog ne. 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.
Year
DOI
Venue
2007
10.1109/IV.2007.84
IV
Keywords
Field
DocType
merging,graph theory,algorithm design and analysis,hypercubes,computer science,visualization,parallel computing,communication networks,distributed computing,broadcasting,approximation algorithms,upper bound
Wheel graph,Combinatorics,Line graph,Hypercube graph,Computer science,Graph homomorphism,Cycle graph,Independent set,Symmetric graph,Complement graph
Conference
ISSN
ISBN
Citations 
1550-6037
0-7695-2900-3
0
PageRank 
References 
Authors
0.34
17
2
Name
Order
Citations
PageRank
Hovhannes A. Harutyunyan120628.18
Xiangyang Xu200.34