Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
By J. Holm, K. H. Lichtenberg, Mikkel Thorup. JACM, 2001
519 citations recorded by the source corpus.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/1f63499a9cb43f0f4d6a56b37de551c7e0c94971
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Amir Abboud
- Virginia Vassilevska Williams
- Marcin Mucha
- Ron Shamir
- Piotr Sankowski
- Igor Ulitsky
- F. Gall
- James B. Orlin
In Computer Networks and Communications
Citations in the corpus
- Identification of functional modules using network topology and high-throughput data (2007, methodology): “Efficient implementation of this algorithm can be done using a data structure similar to the one developed for the dynamic connectivity problem [47].”
- Maximum matchings via Gaussian elimination (2004, methodology): “First of all, we use the dynamic connectivity algorithm of Holm, de Lichtenberg and Thorup [8].”
- Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems (2014, background): “Among its many successes are efficient dynamic graph algorithms for graph connectivity [18], [35], [29], minimum spanning tree [14], [21], [19], graph matching [33], [4], [25], [16] and approximate shortest paths in undirected graphs [5], [6], [17].”