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 alpha (m, n)) time when the edges of E are presorted by weight. The parallel algorithm takes O (log(2)n) time using m processors on a CREW PRAM.