Nearly Linear Time Minimum Spanning TreeMaintenance 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 $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 ${cal O}(m cdot alpha(m,n))$ time and ${cal O}(m)$ space, where $alpha$ is the functional inverse of Ackermanns function. Our solution improves over the previously best known ${cal O}(min{m cdot 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 in E_T$, a replacement edge which can be used for constructing an MST of $G-e=(V,E backslash {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.