Reconstructing a minimum spanning tree after deletion of any node

Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G = (V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G. For each node v in V, the node replacement for v is the minimum weight set of edges R(v) that connect the components of T\v. We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log(n)) time, but only O(mα(m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log2n) time using m processors on a CREW PRAM.