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,E-T) of G, we study the problem of finding, for every node upsilon is an element of V, a set of replacement edges which can be used for constructing an MST of G-upsilon (i.e., the graph G deprived of upsilon 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 log n}) 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 is an element ofE(T), 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.