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.
As a matter of fact, this logarithmic factor was removed in REF , where the authors devised an O(min{m · α(n, n), m + n log n}) time and linear space algorithm.
Maintaining a Minimum Spanning Tree under Transient Node Failures
ICALP
Mathematics Computer Science