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.
Author's Maiden Name: Monika H. Rauch. This research was done while at Cornell University, Ithaca, NY and supported by an NSF CAREER Award, Grant No. CCR-9501712.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon, J. Spencer, P. Erdös. The Probabilistic Method. Wiley-Interscience Series, Johan Wiley and Sons, Inc., 1992.
D. Angluin, L. G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. System Sci. 18 (2), 1979, 155–193.
D. Eppstein, Z. Galil, G. F. Italiano. Improved Sparsification. Tech. Report 93-20, Department of Information and Computer Science, University of California, Irvine, CA 92717.
D. Eppstein, Z. Galil, G. F. Italiano, A. Nissenzweig. Sparsification — A Technique for Speeding up Dynamic Graph Algorithms. Proc. 33rd Symp. on Foundations of Computer Science, 1992, 60–69.
M. L. Fredman and M. R. Henzinger. Lower Bounds for Fully Dynamic Connectivity Problems in Graphs. Submitted to Algorithmica.
M. R. Henzinger and V. King. Randomized Dynamic Graph Algorithms with Polylogarithmic Time per Operation. Proc. 27th ACM Symp. on Theory of Computing, 1995, 519–527.
K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1984.
P. B. Miltersen, S. Subramanian, J. S. Vitter, and R. Tamassia. Complexity models for incremental computation. Theoretical Computer Science, 130, 1994, 203–236.
J. P. Schmidt, A. Siegel, A. Srinivasan. Chernoff-Hoeffding Bounds for Limited Independence. SIAM J. on Discrete Mathematics 8 (2), 1995, 223–250.
R. E. Tarjan and U. Vishkin. Finding biconnected components and computing tree functions in logarithmic paralleltime. SIAM J. Computing, 14(4): 862–874, 1985.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rauch Henzinger, M., Thorup, M. (1996). Improved sampling with applications to dynamic graph algorithms. In: Meyer, F., Monien, B. (eds) Automata, Languages and Programming. ICALP 1996. Lecture Notes in Computer Science, vol 1099. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61440-0_136
Download citation
DOI: https://doi.org/10.1007/3-540-61440-0_136
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61440-1
Online ISBN: 978-3-540-68580-7
eBook Packages: Springer Book Archive