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 isO(V1.6 + E)whereVis the number of nodes and E the number of edges. For dense networks withE ≥ V1.6this order of complexity is optimum.
No takes yet. Share an insight, caveat, or question.
Awerbuch et al. (1987) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: