Hardness of Approximation for Vertex-Connectivity Network Design Problems

DOI10.1137/S0097539702416736zbMath1101.68985MaRDI QIDQ4651489

Robert Krauthgamer, James R. Lee, Guy Kortsarz

Publication date: 21 February 2005

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

zbMATH Keywords

approximation algorithmsvertex connectivityhardness of approximationsurvivable network designconnectivity augmentation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items

Approximating subset \(k\)-connectivity problems ⋮ Hardness of \(k\)-vertex-connected subgraph augmentation problem ⋮ Approximating minimum-cost edge-covers of crossing biset-families ⋮ Correlation clustering and two-edge-connected augmentation for planar graphs ⋮ Unnamed Item ⋮ Approximating node-connectivity augmentation problems ⋮ Improved approximation algorithms for label cover problems ⋮ Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP ⋮ On the computational complexity of measuring global stability of banking networks ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ AN IMPLICIT COVER PROBLEM IN WILD POPULATION STUDY ⋮ An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems ⋮ Kernelization and complexity results for connectivity augmentation problems ⋮ A note on Rooted Survivable Networks ⋮ New Results on the Complexity of the Max- and Min-Rep Problems ⋮ Inapproximability of survivable networks ⋮ On Approximating an Implicit Cover Problem in Biology ⋮ Approximating fault-tolerant group-Steiner problems ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On small-depth tree augmentations

This page was built for publication: Hardness of Approximation for Vertex-Connectivity Network Design Problems