More Web Proxy on the site http://driver.im/

Article

Fully-dynamic min-cut

Author:

Mikkel ThorupAuthors Info & Claims

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

Pages 224 - 230

https://doi.org/10.1145/380752.380804

Published: 06 July 2001 Publication History

Abstract

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in \tilde O(\sqrt{n}) time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^{2/3}), dating back to FOCS'92.

Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in O(\log n) time per edge.

By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in \tilde O(\sqrt{n}) time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a min-cut, but if we want to list the cut edges in O(\log n) time per edge, the update time increases to \tilde O(\sqrt{m}).

References

[1]

S. Alstrup, J. Holm, K. de Lichtenberg, and M. Thorup. Minimizing diameters of dynamic trees. In Proc. 24th Int. Coll. on Automata, Languages, and Programming, LNCS 1256, pages 270-280, 1997.

Digital Library

[2]

S. Alstrup, J. Holm, and M. Thorup. Maintaining center and median in dynamic trees. In Proc. 7th Scandinavian Workshop Algorithms Theory, LNCS 1851, pages 46-56, 2000.

[3]

L. G. Valiant D. Angluin. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. System Sci., 18:155-193, 1979.

[4]

Y. Dinitz and R. Nossenson. Incremental maintenance of the 5-edge-connectivity classes of a graph. In Proc. 7th Scandinavian Workshop Algorithms Theory, LNCS 1851, pages 272-285, 2000.

[5]

D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669-696, 1997. See also FOCS'92.

Digital Library

[6]

D. Eppstein, Z. Galil, G. F. Italiano, and T. H. Spencer. Separator-based sparsification II: Edge and vertex connectivity. SIAM J. Comput., 28:341-381, 1998.

Digital Library

[7]

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

Digital Library

[8]

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

Digital Library

[9]

J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. In Proc. 30th ACM Symp. on Theory of Computing, pages 79-89, 1998.

Digital Library

[10]

D. R. Karger. Using randomized sparsification to approximate minimum cuts. In Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, pages 424-432, 1994.

Digital Library

[11]

D. R. Karger. Minimum cuts in near-linear time. J. ACM, 47(1):46-76, 2000.

Digital Library

[12]

H. Nagamochi and T. Ibaraki. Linear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7:583-596, 1992.

Digital Library

[13]

C. St. J. A. Nash-Williams. Edge disjoint spanning trees of finite graphs. J. London Math. Soc., 36(144):445-450, 1961.

[14]

S. A. Plotkin, D. B. Shmoys, and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20:257-301, 1995.

Digital Library

[15]

D.D. Sleator and R.E. Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sc., 26(3):362-391, 1983. See also STOC'81.

Digital Library

[16]

M. Thorup. Decremental dynamic connectivity. J. Algorithms, 33:229-243, 1999.

Digital Library

[17]

M. Thorup and D. Karger. Dynamic graph algorithms with applications (invited talk). In Proc. 7th Scandinavian Workshop Algorithms Theory, LNCS 1851, pages 1-9, 2000.

[18]

W. T. Tutte. On the problem of decomposing a graph into n connected factors. J. London Math. Soc., 36:221-230, 1961.

[19]

N. Young. Randomized rounding without solving the linear program. In Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 170-178, 1995.

Digital Library

Cited By

Boyd SCheriyan JCummings RGrout LIbrahimpur SSzigeti ZWang L(2022)A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral CaseSIAM Journal on Discrete Mathematics10.1137/20M137282236:3(1730-1747)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/20M1372822
Ghaffari MHaeupler B(2016)Distributed algorithms for planar networks IIProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884451(202-219)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884451
Łącki JSankowski P(2011)Min-cuts and shortest cycles in planar graphs in O(n log log n) timeProceedings of the 19th European conference on Algorithms10.5555/2040572.2040590(155-166)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040590
Show More Cited By

Index Terms

Fully-dynamic min-cut
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Fully-Dynamic Min-Cut

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in $$\ifmmode\expandafter\tilde\else\expandafter\~\fi{O}{\left( {{\sqrt n }} \right)}$$ worst-case time per edge insertion or deletion. Within logarithmic ...
Fully dynamic transitive closure: breaking through the O(n/sup 2/) barrier
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science

We introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure, in particular we devise ...
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

cover image ACM Conferences

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

July 2001

755 pages

ISBN:1581133499

DOI:10.1145/380752

Copyright © 2001 ACM.

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]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC01

Sponsor:

SIGACT

STOC01: 33rd ACM Symposium on Theory of Computing

Hersonissos, Greece

Acceptance Rates

STOC '01 Paper Acceptance Rate 83 of 230 submissions, 36%;

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

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
205
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Boyd SCheriyan JCummings RGrout LIbrahimpur SSzigeti ZWang L(2022)A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral CaseSIAM Journal on Discrete Mathematics10.1137/20M137282236:3(1730-1747)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/20M1372822
Ghaffari MHaeupler B(2016)Distributed algorithms for planar networks IIProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884451(202-219)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884451
Łącki JSankowski P(2011)Min-cuts and shortest cycles in planar graphs in O(n log log n) timeProceedings of the 19th European conference on Algorithms10.5555/2040572.2040590(155-166)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040590
Łącki JSankowski P(2011)Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) TimeAlgorithms – ESA 201110.1007/978-3-642-23719-5_14(155-166)Online publication date: 2011
https://doi.org/10.1007/978-3-642-23719-5_14
Onak KRubinfeld R(2010)Dynamic approximate vertex cover and maximum matchingProperty testing10.5555/1986603.1986634(341-345)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1986603.1986634
Onak KRubinfeld R(2010)Dynamic approximate vertex cover and maximum matchingProperty testing10.5555/1980617.1980648(341-345)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1980617.1980648
Onak KRubinfeld RMitzenmacher MSchulman L(2010)Maintaining a large matching and a small vertex coverProceedings of the forty-second ACM symposium on Theory of computing10.1145/1806689.1806753(457-464)Online publication date: 5-Jun-2010
https://dl.acm.org/doi/10.1145/1806689.1806753
Onak KRubinfeld R(2010)Dynamic Approximate Vertex Cover and Maximum MatchingProperty Testing10.1007/978-3-642-16367-8_28(341-345)Online publication date: 2010
https://doi.org/10.1007/978-3-642-16367-8_28
Kohli PTorr P(2010)Dynamic Graph Cuts and Their Applications in Computer VisionComputer Vision10.1007/978-3-642-12848-6_3(51-108)Online publication date: 2010
https://doi.org/10.1007/978-3-642-12848-6_3
Kohli PTorr P(2007)Dynamic Graph Cuts for Efficient Inference in Markov Random FieldsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2007.112829:12(2079-2088)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1109/TPAMI.2007.1128
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten