Dynamically Reconstructing Minimum Spanning Trees After Swapping Pairwise Vertices

Abstract

The minimum spanning tree (MST) problem is a fundamental problem in computer science and operations research, which has many real-life network design applications. Given a graph G with n vertices and m edges, starting from an MST (denoted by T) covering a subgraph of G, it is usually needed to reconstruct a new MST after swapping two vertices v ∈ T and v' ∉ T. For this purpose, the most popular choice is to reconstruct an MST from scratch, for which the current fastest algorithm (Kruskal's algorithm based on Fibonacci heap) requires a time complexity of O(m + n · log n), implying that a high time complexity of O(n2) · O(m + n · log n) is needed to evaluate all the O(n2) possible swapping-based moves. In order to evaluate these moves more efficiently, we integrate a series of dynamic techniques to develop a fast dynamic swap-vertex move operator, which significantly reduces the overall time complexity from O(n2) · O(m + n · log n) to O(n) · O(m · log n). We also strictly prove the correctness of the introduced method. Finally, we choose three well-studied Steiner/spanning tree problems as our test bed and carry out extensive experiments on 140 representative instances to show the effectiveness and efficiency of the proposed method. More importantly, as a general-purpose method, the dynamic swap-vertex move operator could be easily adapted to many other tree-related problems.

Keywords

• Dynamic data structure
• Steiner/spanning tree problems
• swap-vertex move operator