Fully-dynamic MIN-cut

DOI10.1145/380752.380804MaRDI QIDQ5175972zbMATH OpenOpenAlexFDO

Authors Mikkel Thorup

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/380752.380804

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Fully-dynamic min-cut
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Approximating minimum cuts under insertions
• Incremental exact min-cut in polylogarithmic amortized update time

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(14)

• Incremental algorithm for minimum cut and edge connectivity in hypergraph
• scientific article; zbMATH DE number 1617266 (Why is no real title available?)
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• Incremental exact min-cut in polylogarithmic amortized update time
• Approximating minimum cuts under insertions
• Fast and simple fully-dynamic cut tree construction
• Dynamic approximate vertex cover and maximum matching
• A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
• An improved algorithm for incremental DFS tree in undirected graphs
• Practical fully dynamic minimum cut algorithms
• Fully dynamic sequential and distributed algorithms for MAX-CUT
• Stable and dynamic minimum cuts
• Fully-dynamic min-cut
• Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity

This page was built for publication: Fully-dynamic MIN-cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175972)