A new distributed algorithm to find breadth first search trees
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 O(V^{1.6} + E) where V is the number of nodes and E the number of edges. For dense networks with E \geq V^{1.6} this order of complexity is optimum.