Approximating minimum-cost connectivity problems via uncrossable bifamilies
From MaRDI portal
Publication:2933629
DOI10.1145/2390176.2390177zbMath1301.68275OpenAlexW2052656799MaRDI QIDQ2933629
Publication date: 5 December 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2390176.2390177
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 (18)
Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating \(k\)-connected \(m\)-dominating sets ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Unnamed Item ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ Approximating k-Connected m-Dominating Sets ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Covering problems in edge- and node-weighted graphs ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ Approximating source location and star survivable network problems ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems ⋮ Approximating Source Location and Star Survivable Network Problems
This page was built for publication: Approximating minimum-cost connectivity problems via uncrossable bifamilies
