An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
From MaRDI portal
Publication:5171193
DOI10.1109/FOCS.2009.38zbMath1292.68090MaRDI QIDQ5171193
Publication date: 25 July 2014
Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (18)
Approximating subset \(k\)-connectivity problems ⋮ Unnamed Item ⋮ Approximating node-connectivity augmentation problems ⋮ Degree constrained node-connectivity problems ⋮ Black-box reductions for cost-sharing mechanism design ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ Approximability of Capacitated Network Design ⋮ An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity ⋮ Approximating source location and star survivable network problems ⋮ Simpler analysis of LP extreme points for traveling salesman and survivable network design problems ⋮ Approximating survivable networks with \(\beta \)-metric costs ⋮ A note on Rooted Survivable Networks ⋮ Approximating Survivable Networks with Minimum Number of Steiner Points ⋮ Approximating Source Location and Star Survivable Network Problems ⋮ A note on labeling schemes for graph connectivity ⋮ Approximating fault-tolerant group-Steiner problems ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
