A kinetic minimum spanning tree is a kinetic data structure that maintains the minimum spanning tree (MST) of a graph whose edge weights are changing as a continuous function of time.
The most efficient known data structure for the general case uses a kinetic sorted list to store the edge weights, and a standard MST algorithm to compute the MST given the sorted edge weights.
events, developing a more efficient data structure remains an open problem.
[1] Agarwal et al. developed a data structure that maintains the MST for a graph belonging to a minor closed family.
This data structure considers the dual view of the graph, and then divides based on Frederickson's restricted partitions [2] to make this efficient.
These deterministic bounds are slightly improved if randomization is allowed.