Article

Free access

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

Authors:

Jacob Holm,

Kristian de Lichtenberg,

Mikkel ThorupAuthors Info & Claims

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

Pages 79 - 89

https://doi.org/10.1145/276698.276715

Published: 23 May 1998 Publication History

PDF eReader

References

[1]

S, Alstrup, J. Holm, K. de Lichtenberg, and M. Thorup. Minimizing diameters of dynamic trees. In Prec. 24th International Colloquhon on Automata, Languages, and Programmhtg (ICALP), pages 270--280, 1997.

Digital Library

Google Scholar

[2]

D. Eppstein. Dynamic euclidean minimum spanning trees and extrema of binary functions. Discrete Comput. Geom., 13:237-250, 1995.

Digital Library

Google Scholar

[3]

D. Eppstein, Z. Galil, (3. E Italiano, and A. Nissenzweig. Sparsification-- a technique for speeding up dynamic graph algorithms. Journal of the ACM, 44(5):669--696, September 1997. See also FOCS'92.

Digital Library

Google Scholar

[4]

S. Even and Y. Shiloach. An on-line edge-deletion problem. Journal of the ACM, 28(1):1--4, January 1981.

Digital Library

Google Scholar

[5]

G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Computing, 14(4):781--798, 1985. See also STOC'83.

Digital Library

Google Scholar

[6]

G.N. Frederickson. Ambivalent data structures for dynamic 2-Edge-Connectivity and k smallest spanning trees. SIAM Journal on Computing, 26(2):484-538, April 1997. See also FOCS'91.

Digital Library

Google Scholar

[7]

M. Fredman and M. R. Henzinger. Lower bounds for fully dynamic connectivity problems in graphs. Technical Report TR95-1523, Cornell University, Computer Science, 1995. To appear inAlgorithmica. See also STOC'94 {16}.

Digital Library

Google Scholar

[8]

M. R. Henzinger. Fully dynamic biconnectivity in graphs. Algorithmica, 13(6):503-.538, June 1995. See also FOCS'92.

Digital Library

Google Scholar

[9]

M. R. Henzinger and V. King. Fully dynamic biconnectivity and transitive closure, in Proc. 36th IEEE S)vnp. Foundations of Computer Science, pages 664-672, .1995.

Digital Library

Google Scholar

[10]

M. R. Henzinger and V. King. Randomized dynamic graph algorithms with polylogarithmie time per operation. In Proc. 27th Symp. on Theory of Computing, pages 519--527, 1995.

Digital Library

Google Scholar

[11]

M.R. Henzinger and V. King. Fully dynamic 2-edge connectivity algorithm in polygarithmic time per operation. Technical Report SRC 1997-004a, Digital, 1997. A preliminary version appeared as {10}.

Google Scholar

[12]

M. R. Henzinger and V. King. Maintaining minimum spanning trees in dynamic graphs. In Prec. 24th International Colloquium on Automata, Languages, and Programming (ICALP), pages 594--6~, 1997.

Digital Library

Google Scholar

[13]

M. R. Henzinger and H. La Poutr6. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In Prec. 3rd European S)~p. Algorithms, LNCS 979, pages 171-184, 1995.

Crossref

Google Scholar

[14]

M. R. Henzinger and M. Thorup. Sampling to provide or to bound: With applictions to fully dynamic graph algorithms. Random Structures and Algorithms, 11:369--379, 1997. See also ICALP'96.

Digital Library

Google Scholar

[15]

P.B. Miltersen, S. Subramanian, J. S. Vitter, and R. Tamassia. Complexity models for incremental computation. Theoretical Computer Science, 130(1):203-236, 1994.

Digital Library

Google Scholar

[16]

M. Rauch. Improved data structures for fully dynamic biconnectivity. In Proceedings of the Twenty-Sixth Annual ACM S)vnposium on Theory of Computing, may 1994.

Digital Library

Google Scholar

[17]

D.D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. of Computer and System Sciences, 26:362-390, 1983.

Digital Library

Google Scholar

[18]

R. E. Tarjan. Efficiency of a good but not linear set union algorithms. J. Assoc. Comput. Mach., 22:215-225, 1975.

Digital Library

Google Scholar

[19]

M. Thorup. Decremental dynamic connectivity. In Proceedings of the 8th ACM. SIAM Symposium on Discrete Algorithms (SODA), pages 305-313, 1997.

Digital Library

Google Scholar

[20]

J. Westbrook and R. E. Tarjan. Maintaining bridge-connected and biconnected components on-line. Algorithmica, 7:433-- 464, 1992.

Crossref

Google Scholar

Cited By

View all

Zhang CBonifati AÖzsu M(2024)Incremental Sliding Window Connectivity over Streaming GraphsProceedings of the VLDB Endowment10.14778/3675034.367504017:10(2473-2486)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.14778/3675034.3675040
Christiansen ANowicki KRotenberg ESaha BServedio R(2023)Improved Dynamic Colouring of Sparse GraphsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585111(1201-1214)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585111
Hanauer KHenzinger MSchulz C(2022)Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference GuideACM Journal of Experimental Algorithmics10.1145/355580627(1-45)Online publication date: 13-Dec-2022
https://dl.acm.org/doi/10.1145/3555806
Show More Cited By

Index Terms

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Trees
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O(log² n) for ...
Spanning tree packing and 2-essential edge-connectivity
Abstract
An edge (vertex) cut X of G is r-essential if G − X has two components each of which has at least r edges. A graph G is r-essentially k-edge-connected (resp. k-connected) if it has no r-essential edge (resp. vertex) cuts of size less ...
Faster deterministic fully-dynamic graph connectivity
SODA '13: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms

We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions/deletions) in O(log² n/log log n) amortized time and connectivity queries in O(log n/log log n) worst-case time, where n is the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

May 1998

684 pages

ISBN:0897919629

DOI:10.1145/276698

Chairman:
Jeffrey Vitter

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC98

Sponsor:

SIGACT

STOC98: The 30th Annual ACM Symposium on Theory of Computing

May 24 - 26, 1998

Texas, Dallas, USA

Acceptance Rates

STOC '98 Paper Acceptance Rate 75 of 169 submissions, 44%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
922
Total Downloads

Downloads (Last 12 months)109
Downloads (Last 6 weeks)14

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang CBonifati AÖzsu M(2024)Incremental Sliding Window Connectivity over Streaming GraphsProceedings of the VLDB Endowment10.14778/3675034.367504017:10(2473-2486)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.14778/3675034.3675040
Christiansen ANowicki KRotenberg ESaha BServedio R(2023)Improved Dynamic Colouring of Sparse GraphsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585111(1201-1214)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585111
Hanauer KHenzinger MSchulz C(2022)Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference GuideACM Journal of Experimental Algorithmics10.1145/355580627(1-45)Online publication date: 13-Dec-2022
https://dl.acm.org/doi/10.1145/3555806
Chuzhoy JGao YLi JNanongkai DPeng RSaranurak T(2020)A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00111(1158-1167)Online publication date: Nov-2020
https://doi.org/10.1109/FOCS46700.2020.00111
Peng RSandlund BSleator D(2019)Optimal Offline Dynamic 2, 3-Edge/Vertex ConnectivityAlgorithms and Data Structures10.1007/978-3-030-24766-9_40(553-565)Online publication date: 12-Jul-2019
https://doi.org/10.1007/978-3-030-24766-9_40
Holm JRotenberg EThorup MCzumaj A(2018)Dynamic bridge-finding in õ(log2 n) amortized timeProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175269(35-52)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175269
Censor-Hillel KHaramaty EKarnin ZGiakkoupis G(2016)Optimal Dynamic Distributed MISProceedings of the 2016 ACM Symposium on Principles of Distributed Computing10.1145/2933057.2933083(217-226)Online publication date: 25-Jul-2016
https://dl.acm.org/doi/10.1145/2933057.2933083
Mashayekhi HHabibi JVoulgaris SSteen M(2013)GoSCANComputing10.1007/s00607-012-0264-295:9(759-784)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1007/s00607-012-0264-2
Paschos SPaschos V(2012)Reoptimization of the minimum spanning treeWIREs Computational Statistics10.1002/wics.2044:2(211-217)Online publication date: 7-Feb-2012
https://dl.acm.org/doi/10.1002/wics.204
LeBras RDamoulas TGregoire JSabharwal AGomes Cvan Dover R(2011)Constraint Reasoning and Kernel Clustering for Pattern Decomposition with ScalingPrinciples and Practice of Constraint Programming – CP 201110.1007/978-3-642-23786-7_39(508-522)Online publication date: 2011
https://doi.org/10.1007/978-3-642-23786-7_39
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

Spanning tree packing and 2-essential edge-connectivity

Faster deterministic fully-dynamic graph connectivity