Maintaining a Minimum Spanning Tree under Transient Node Failures

Given a 2-node connected, undirected graph G = (V,E), with n nodes and m edges with real weights, and given a minimum spanning tree (MST) T = (V,ET) of G, we study the problem of finding, for every node v ∈ V, the MST of G - v =(V\{v},E\Ev), where Ev is the set of edges incident to v in G. We show that this problem can be solved in O(min(m ċ α (n, n), m+n log n)) time and O(m) space. Our solution improves on the previously known O(m log n) time bound.