An Efficient Distributed Algorithm to Solve Breadth-First spanning Tree Updating Problem

Consider the problem to updata breadth-First Spanning Tree in response to topology change of the network. The paper proposes an efficient distributed algorithm that solves such a problem after several processors and links are added and deleted. Its message complexity and its ideal-time complexity are O(p√q+q+a+n') respectively, where n' is the number fo processors in the network after the topology change, a is the number of added links, p is the total number of links in the biconnected component (of the network before the topology change) including the detected links or added links, and q is the total number of processors in the biconnected component (of the network before the topology change) including the deleted links or added links, and q is the total number of processors in the biconnected component including the deleted links or added links.