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

DOI10.1137/S0097539701392287MaRDI QIDQ4429672zbMATH OpenOpenAlexFDO

Authors Adrian Vetta, Joseph Cheriyan, Santosh S. Vempala

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

\(\ell\)-critically \(k\)-connected graph\(k\)-outconnected graphapproximation algorithmlinear programming relaxationnetwork designvertex connectivity

Mathematics Subject Classification ID

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

Recommendations

• An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
• Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
• An improved approximation algorithm for minimum-cost subset k-connectivity (extended abstract)
• Publication:4886063
• An approximation algorithm for minimum-cost vertex-connectivity problems

Cited in

(30)

• On k-connectivity problems with sharpened triangle inequality
• Approximating minimum-power edge-covers and 2,3-connectivity
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• Approximation algorithms for connected graph factors of minimum weight
• Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
• A 4+ approximation for k-connected subgraphs
• Approximating minimum-cost connected \(T\)-joins
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Approximation algorithms for k-connected graph factors
• A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
• Approximation algorithms for minimum-cost k-(S,T) connected digraphs
• A dual-fitting \(\frac{3}{2}\)-approximation algorithm for some minimum-cost graph problems
• Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• An improved approximation algorithm for minimum-cost subset k-connectivity (extended abstract)
• scientific article; zbMATH DE number 1817738 (Why is no real title available?)
• scientific article; zbMATH DE number 4029292 (Why is no real title available?)
• Approximating minimum-cost edge-covers of crossing biset-families
• scientific article; zbMATH DE number 1305417 (Why is no real title available?)
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
• scientific article; zbMATH DE number 910889 (Why is no real title available?)
• An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
• An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
• Approximating k-node Connected Subgraphs via Critical Graphs
• Improved approximation algorithms for min-cost connectivity augmentation problems
• On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
• An approximation algorithm for minimum-cost vertex-connectivity problems
• Power optimization for connectivity problems

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

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