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

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)

Cited In (8)

• Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity
• Title not available (Why is that?)
• Improved approximations for relative survivable network design
• Title not available (Why is that?)
• Sparse connectivity certificates via MA orderings in graphs
• 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

Recommendations

• Title not available (Why is that?) 👍 👎
• Fully-dynamic min-cut 👍 👎
• Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time 👍 👎
• The connectivity carcass of a vertex subset in a graph and its incremental maintenance 👍 👎
• Approximating minimum cuts under insertions 👍 👎

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)