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 real weights, given minimum spanning tree (MST) T (V,ET) of G, we study the problem finding, for every node v ∈ V, MST - =(V\{v},E\Ev), where Ev is set incident to in G. We show that this can be solved O(min(m ċ α (n, n), m+n log n)) time O(m) space. Our solution improves on previously known O(m n) bound.