Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions

DOI10.1109/FOCS.2009.9zbMath1292.68170OpenAlexW2163193155MaRDI QIDQ5171191

Zeev Nutov

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.9

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (17)

Approximating subset \(k\)-connectivity problems ⋮ Survivable network activation problems ⋮ Unnamed Item ⋮ Approximating node-connectivity augmentation problems ⋮ Multi-priority graph sparsification ⋮ Approximating minimum cost source location problems with local vertex-connectivity demands ⋮ Degree constrained node-connectivity problems ⋮ 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 ⋮ Approximating survivable networks with \(\beta \)-metric costs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ A note on Rooted Survivable Networks ⋮ Approximating fault-tolerant group-Steiner problems ⋮ Unnamed Item ⋮ Approximability of capacitated network design ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs

This page was built for publication: Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions