Nearly Linear Time Minimum Spanning Tree Maintenance for Transient Node Failures

Given a 2-node connected, real weighted, and undirected graph G=(V,E), with n nodes and m edges, and given a minimum spanning tree (MST) T=(V,ET) of G, we study the problem of finding, for every node v in V, a set of replacement edges which can be used for constructing an MST of G-v (i.e., the graph G deprived of v and all its incident edges). We show that this problem can be solved on a pointer machine in O(m ·alpha(m,n)) time and O(m) space, where alpha() is the functional inverse of Ackermann’s function. Our solution improves over the previously best known O(min{m ·alpha(n,n), m + n logn}) time bound, and allows us to close the gap existing with the fastest solution for the edge-removal version of the problem (i.e., that of finding, for every edge e in ET, a replacement edge which can be used for constructing an MST of G-e=(V,E\{e}). Our algorithm finds immediate application in maintaining MST-based communication networks undergoing temporary node failures. Moreover, in a distributed environment in which nodes are managed by selfish agents, it can be used to design an efficient, truthful mechanism for building an MST.