Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
From MaRDI portal
Publication:5171191
DOI10.1109/FOCS.2009.9zbMath1292.68170MaRDI QIDQ5171191
Publication date: 25 July 2014
Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68W25: Approximation algorithms
05C40: Connectivity
Related Items
Unnamed Item, Unnamed Item, Survivable network activation problems, Degree constrained node-connectivity problems, Approximating survivable networks with \(\beta \)-metric costs, Approximating fault-tolerant group-Steiner problems, A note on Rooted Survivable Networks, Approximability of capacitated network design, Approximating subset \(k\)-connectivity problems, Approximating node-connectivity augmentation problems, Approximating minimum cost source location problems with local vertex-connectivity demands, Approximability of Capacitated Network Design, Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands, An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity