Hardness of Approximation for Vertex-Connectivity Network Design Problems
From MaRDI portal
Publication:4651489
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)
approximation algorithms; vertex connectivity; hardness of approximation; survivable network design; connectivity augmentation
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
05C40: Connectivity
Related Items
Unnamed Item, Unnamed Item, Approximating minimum-cost edge-covers of crossing biset-families, On the computational complexity of measuring global stability of banking networks, An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem, Hardness of \(k\)-vertex-connected subgraph augmentation problem, Improved approximation algorithms for label cover problems, Approximating fault-tolerant group-Steiner problems, A note on Rooted Survivable Networks, Inapproximability of survivable networks, Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP, On the approximability and hardness of the minimum connected dominating set with routing cost constraint, Approximating subset \(k\)-connectivity problems, Approximating node-connectivity augmentation problems, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity, Kernelization and complexity results for connectivity augmentation problems, New Results on the Complexity of the Max- and Min-Rep Problems, AN IMPLICIT COVER PROBLEM IN WILD POPULATION STUDY, On Approximating an Implicit Cover Problem in Biology
