A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity

DOI10.1006/JAGM.1997.0855zbMATH Open0879.68045OpenAlexW2038708787MaRDI QIDQ4349705FDOQ4349705

Authors: Monika R. Henzinger 

Publication date: 12 January 1998

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/3190216f8e7d1220a85ef13edf0e7e086f49ecd3

Recommendations

• Approximating minimum cuts under insertions
• Fully-dynamic MIN-cut
• scientific article; zbMATH DE number 437577
• The connectivity carcass of a vertex subset in a graph and its incremental maintenance
• Incremental exact min-cut in polylogarithmic amortized update time

zbMATH Keywords

insertions-only algorithms

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Cited In (14)

• Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity
• Title not available (Why is that?)
• Approximating minimum cuts under insertions
• Improved approximations for relative survivable network design
• Breaking quadratic time for small vertex connectivity and an approximation scheme
• Title not available (Why is that?)
• Sparse connectivity certificates via MA orderings in graphs
• Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness
• The connectivity carcass of a vertex subset in a graph and its incremental maintenance
• Incremental exact min-cut in polylogarithmic amortized update time
• Engineering nearly linear-time algorithms for small vertex connectivity
• Computing vertex-disjoint paths in large graphs using MAOs
• Optimal offline dynamic \(2\), \(3\)-edge/vertex connectivity
• Fully-dynamic MIN-cut

This page was built for publication: A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity

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