New Distributed Algorithm to Find Breadth First Search Trees

摘要

A new distributed algorithm is presented for constructing breadth first search (BFS) tress. 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 communications networks. The order of communication complexity for the new algorithms is o((v to the 1.6 power) + E) where v is the number of nodes and E the number of edges. For dense networks with E = or > V to the 1.6 power, this order of complexity is optimum.