Fully Retroactive Minimum Spanning Tree Problem. (8th December 2020)

• Record Type: Journal Article
• Authors: de Andrade Júnior, José Wagner; Duarte Seabra, Rodrigo
• Is Part Of: Computer journal. Volume 65:Number 4(2022)
• Page Start: 973
• Page End: 982
• Publication Date: 2020-12-08
• Subjects: minimum spanning tree -- retroactivity -- data structures -- dynamic graphs; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa135
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: This article describes an algorithm that solves a fully dynamic variant of the minimum spanning tree (MST) problem. The fully retroactive MST allows adding an edge to time $t$, or to obtain the current MST at time $t$ . By using the square root technique and a data structure link-cut tree, it was possible to obtain an algorithm that runs each query in $O(\sqrt{m} \lg{|V(G)|})$ amortized, in which $|V(G)|$ is the number of nodes in graph $G$ and $m$ is the size of the timeline. We use a different approach to solve the MST problem instead of the standard algorithms, such as Prim or Kruskal, and this allows using the square root technique to improve the final complexity of the algorithm. Our empirical analysis shows that the proposed algorithm runs faster than re-executing the standard algorithms, and this difference only increases when the number of nodes in these graphs is larger.