Approximating Minimum-Cost $k$-Node Connected Subgraphs via Independence-Free Graphs

DOI10.1137/120902847zbMath1303.05097arXiv1212.3981OpenAlexW2178196238MaRDI QIDQ2929700

László A. Végh, Joseph Cheriyan

Publication date: 14 November 2014

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

Full work available at URL: https://arxiv.org/abs/1212.3981

zbMATH Keywords

linear programminggraph connectivityapproximation algorithmsiterative rounding

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (11)

Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ A Spectral Approach to Network Design ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ A unified algorithm for degree bounded survivable network design ⋮ On the fixed-parameter tractability of the maximum connectivity improvement problem ⋮ Unnamed Item ⋮ Approximating k-Connected m-Dominating Sets ⋮ Approximating minimum power edge-multi-covers ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems

This page was built for publication: Approximating Minimum-Cost $k$-Node Connected Subgraphs via Independence-Free Graphs