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

DOI10.1006/JAGM.1997.0855MaRDI QIDQ4349705zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

insertions-only algorithms

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

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

Cited in

(14)

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

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)