Approximating Minimum-Cost $k$-Node Connected Subgraphs via Independence-Free Graphs
From MaRDI portal
Publication:2929700
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
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
