Kinetic minimum spanning tree

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.

General case

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. This data structure must process events, developing a more efficient data structure remains an open problem.[1]

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 e was replaced by an edge f outside the tree such that the circle induced by f in the tree contains e. 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 view of the graph, and then divides based on Frederickson's restricted partitions [2] to make this efficient. It results in a total run time if insertions or deletions are made, or if only weight changes are allowed. These deterministic bounds are slightly improved if randomization is allowed.

gollark: I wouldn't verify personal detail disclosure like this without using a really slow hash anyway.
gollark: Less if you have a bit of money and rent a GPU computing server. Or just "borrow" Google Colab for free.
gollark: You could also just bruteforce the hash of the name in probably at most an hour with a good GPU assuming my wild assumptions.
gollark: Maybe an order of magnitude or so slower as it is slower to check.
gollark: Krist mining can do a few GH/s on a good GPU, and that's SHA256, so you could bruteforce the entire practical namespace in 100 seconds.

References
  1. Demaine, Erik D. MIT 6.851 Advanced Data Structures, lecture video.
  2. Frederickson, G. N. (1997). "Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees". SIAM Journal on Computing: 484–538. doi:10.1137/s0097539792226825.

Further reading

Agarwal, Pankaj; Eppstein, David; Guibas, Leonidas J.; Henzinger, Monika R. (1998). Parametric and Kinetic Minimum Spanning Trees (PDF). FOCS. Retrieved May 19, 2012.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.