Fully Retroactive Minimum Spanning Tree Problem

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 , or to obtain the current MST at time . 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 amortized, in which is the number of nodes in graph and 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.

Automated summary

This article describes an algorithm that solves a fully dynamic variant of the minimum spanning tree problem. The algorithm achieves an amortized time complexity of O(√n log m) per query by using the square root technique and a data structure called link-cut tree. Instead of using the standard algorithms like Prim or Kruskal, this algorithm takes a different approach to solve the MST problem and improves its complexity with the square root technique. Empirical analysis shows that the proposed algorithm outperforms the standard algorithms, especially when the number of nodes in the graph is large.