Improved approximation algorithms for minimum cost node-connectivity augmentation problems
From MaRDI portal
Publication:1635806
DOI10.1007/s00224-017-9786-5zbMath1394.68443OpenAlexW2620883502MaRDI QIDQ1635806
Publication date: 1 June 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-017-9786-5
Related Items (5)
\(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ On the fixed-parameter tractability of the maximum connectivity improvement problem ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
Cites Work
- Approximating minimum-cost edge-covers of crossing biset-families
- An approximation algorithm for minimum-cost vertex-connectivity problems
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Inapproximability of survivable networks
- Rooted \(k\)-connections in digraphs
- An application of submodular flows
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Approximating node connectivity problems via set covers
- Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
- On the optimal vertex-connectivity augmentation
- Minimal edge-coverings of pairs of sets
- A bad example for the iterative rounding method for mincost \(k\)-connected spanning subgraphs
- Approximating subset \(k\)-connectivity problems
- Approximating node-connectivity augmentation problems
- Approximating minimum cost source location problems with local vertex-connectivity demands
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation
- Approximating Source Location and Star Survivable Network Problems
- Approximation Algorithms for Minimum-Cost $k\hbox{-}(S,T)$ Connected Digraphs
- Approximating Minimum-Cost $k$-Node Connected Subgraphs via Independence-Free Graphs
- Approximating minimum-cost connectivity problems via uncrossable bifamilies
- Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
- Augmenting Undirected Node-Connectivity by One
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
- Improved Approximation Algorithms for Uniform Connectivity Problems
- An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem
- Approximating Rooted Steiner Networks
- Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
- Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
- Approximating k-node Connected Subgraphs via Critical Graphs
- Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems
- Unnamed Item
- Unnamed Item
This page was built for publication: Improved approximation algorithms for minimum cost node-connectivity augmentation problems
