A kinetic minimum spanning tree is a kinetic data structure that maintains the

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

(MST) of a graph whose edge weights are changing as a continuous function of time.

General case

The most efficient known data structure for the general case uses a

kinetic sorted list A kinetic sorted list is a kinetic data structure for maintaining a list of points under motion in sorted order. It is used as a kinetic predecessor data structure, and as a component in more complex kinetic data structures such as kinetic clos ...

to store the edge weights, and a standard MST algorithm to compute the MST given the sorted edge weights. This data structure must process

O(n^2)

events, developing a more efficient data structure remains an open problem.

H-minor-free graphs

Agarwal ''et al.'' developed a data structure that maintains the MST for a graph belonging to a minor closed family. It uses the idea of a "swap", calculating the amount by which the weight of the MST would increase if some edge in the tree was replaced by an edge outside the tree such that the circle induced by in the tree contains . Maintaining the tree is then equivalent to finding and swapping the next pair for which this quantity becomes negative. This data structure considers the

dual Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual (grammatical ...

view of the graph, and then

divides In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...

based on Frederickson's restricted partitions to make this efficient. It results in a total run time

O(pn^\log^n)

p

insertions or deletions are made, or

O(n^\log^n)

if only weight changes are allowed. These deterministic bounds are slightly improved if randomization is allowed.

General case

H-minor-free graphs

References

Further reading