An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph

DOI10.1137/S0097539701392287zbMath1029.68158OpenAlexW1986011879MaRDI QIDQ4429672

Adrian Vetta, Santosh Vempala, Joseph Cheriyan

Publication date: 28 September 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539701392287

zbMATH Keywords

approximation algorithmnetwork designlinear programming relaxationvertex connectivity\(\ell\)-critically \(k\)-connected graph\(k\)-outconnected graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (13)

Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Power optimization for connectivity problems ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Approximating minimum-cost edge-covers of crossing biset-families ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Approximating Survivable Networks with Minimum Number of Steiner Points ⋮ Approximating minimum-power edge-covers and 2,3-connectivity

This page was built for publication: An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph