Abstract. 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 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.
In this paper we provide an improved version of the algorithm presented in REF , running in O(m · α(m, n)) time and using O(m) space.
Maintaining a Minimum Spanning Tree under Transient Node Failures
ICALP
Mathematics Computer Science