DocumentCode :
942986
Title :
A new distributed algorithm to find breadth first search trees
Author :
Awerbuch, Baruch ; Gallager, Robert G.
Volume :
33
Issue :
3
fYear :
1987
fDate :
5/1/1987 12:00:00 AM
Firstpage :
315
Lastpage :
322
Abstract :
A new distributed algorithm is presented for constructing breadth first search (BFS) trees. A BFS tree is a tree of shortest paths from a given root node to all other nodes of a network under the assumption of unit edge weights; such trees provide useful building blocks for a number of routing and control functions in communication networks. The order of communication complexity for the new algorithm is 
where 
is the number of nodes and E the number of edges. For dense networks with 
this order of complexity is optimum.
where is the number of nodes and E the number of edges. For dense networks with this order of complexity is optimum.Keywords :
Networks; Tree coding; Asynchronous communication; Bidirectional control; Bridges; Communication networks; Communication system control; Complexity theory; Delay effects; Distributed algorithms; Routing; Tree graphs;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1987.1057314
Filename :
1057314
Link To Document :
