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)
68Q25: Analysis of algorithms and problem complexity
68M10: Network design and communication in computer systems
68R10: Graph theory (including graph drawing) in computer science
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
Unnamed Item, Unnamed Item, Degree constrained node-connectivity problems, An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem, Approximating source location and star survivable network problems, Approximating survivable networks with \(\beta \)-metric costs, A note on labeling schemes for graph connectivity, Approximating fault-tolerant group-Steiner problems, Simpler analysis of LP extreme points for traveling salesman and survivable network design problems, A note on Rooted Survivable Networks, Black-box reductions for cost-sharing mechanism design, Approximating subset \(k\)-connectivity problems, Approximating node-connectivity augmentation problems, Approximating Source Location and Star Survivable Network Problems, Approximability of Capacitated Network Design, An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity, Approximating Survivable Networks with Minimum Number of Steiner Points
