Improved sampling with applications to dynamic graph algorithms

Henzinger MH, Thorup M. 1996. Improved sampling with applications to dynamic graph algorithms. 23rd International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 1099, 290–299.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English

Scopus indexed
Author
Henzinger, MonikaISTA ; Thorup, Mikkel
Series Title
LNCS
Abstract
We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms. For the dynamic connectivity problem the previously best randomized algorithm takes expected time O(log3 n) per update, amortized over Ω(m) updates. Using the new sampling lemma, we improve its running time to O(log2 n). There exists a lower bound in the cell probe model for the time per operation of Ω(log n/ log log n) for this problem. Similarly improved running times are achieved for 2-edge connectivity, k-weight minimum spanning tree, and bipartiteness.
Publishing Year
Date Published
1996-07-01
Proceedings Title
23rd International Colloquium on Automata, Languages, and Programming
Publisher
Springer Nature
Volume
1099
Page
290-299
Conference
ICALP: International Colloquium on Automata, Languages, and Programming
Conference Location
Paderborn, Germany
Conference Date
1996-07-08 – 1996-07-12
ISSN
eISSN
IST-REx-ID

Cite this

Henzinger MH, Thorup M. Improved sampling with applications to dynamic graph algorithms. In: 23rd International Colloquium on Automata, Languages, and Programming. Vol 1099. Springer Nature; 1996:290-299. doi:10.1007/3-540-61440-0_136
Henzinger, M. H., & Thorup, M. (1996). Improved sampling with applications to dynamic graph algorithms. In 23rd International Colloquium on Automata, Languages, and Programming (Vol. 1099, pp. 290–299). Paderborn, Germany: Springer Nature. https://doi.org/10.1007/3-540-61440-0_136
Henzinger, Monika H, and Mikkel Thorup. “Improved Sampling with Applications to Dynamic Graph Algorithms.” In 23rd International Colloquium on Automata, Languages, and Programming, 1099:290–99. Springer Nature, 1996. https://doi.org/10.1007/3-540-61440-0_136.
M. H. Henzinger and M. Thorup, “Improved sampling with applications to dynamic graph algorithms,” in 23rd International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 1996, vol. 1099, pp. 290–299.
Henzinger MH, Thorup M. 1996. Improved sampling with applications to dynamic graph algorithms. 23rd International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 1099, 290–299.
Henzinger, Monika H., and Mikkel Thorup. “Improved Sampling with Applications to Dynamic Graph Algorithms.” 23rd International Colloquium on Automata, Languages, and Programming, vol. 1099, Springer Nature, 1996, pp. 290–99, doi:10.1007/3-540-61440-0_136.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search