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

DOI10.1006/jagm.1997.0855zbMath0879.68045OpenAlexW2038708787MaRDI QIDQ4349705

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)

Related Items (4)

Sparse connectivity certificates via MA orderings in graphs ⋮ Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity ⋮ Unnamed Item ⋮ Computing vertex-disjoint paths in large graphs using MAOs

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