A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
From MaRDI portal
Publication:2237891
DOI10.1016/j.jcss.2021.07.006zbMath1472.68215arXiv1901.07246OpenAlexW3189164058MaRDI QIDQ2237891
Publication date: 28 October 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1901.07246
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Connectivity (05C40)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating minimum-cost edge-covers of crossing biset-families
- Network design via iterative rounding of setpair relaxations
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
- Inapproximability of survivable networks
- Rooted \(k\)-connections in digraphs
- An application of submodular flows
- On the relationship between the biconnectivity augmentation and traveling salesman problems
- Approximating node connectivity problems via set covers
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Independence free graphs and vertex connectivity augmentation
- Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Minimal edge-coverings of pairs of sets
- A bad example for the iterative rounding method for mincost \(k\)-connected spanning subgraphs
- Small \(\ell\)-edge-covers in \(k\)-connected graphs
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
- 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
- A Survey on Covering Supermodular Functions
- Augmenting Undirected Node-Connectivity by One
- Approximation Algorithms for Several Graph Augmentation Problems
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- 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
- Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
- Approximating k-node Connected Subgraphs via Critical Graphs
