Approximation algorithms for vertex-connectivity augmentation on the cycle
From MaRDI portal
Publication:2085731
DOI10.1007/978-3-030-92702-8_1OpenAlexW4285524729MaRDI QIDQ2085731
Francisco Sanhueza-Matamala, Waldo Gálvez, Jose A. Soto
Publication date: 19 October 2022
Full work available at URL: https://arxiv.org/abs/2111.02234
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- On the integrality ratio for tree augmentation
- LP-relaxations for tree augmentation
- Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- 2-node-connectivity network design
- On the cycle augmentation problem: hardness and approximation algorithms
- Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
- On the tree augmentation problem
- Augmenting Undirected Node-Connectivity by One
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximation Algorithms for Graph Augmentation
- Recognition of Circle Graphs
- Biconnectivity approximations and graph carvings
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
- A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
- A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
- A 4 + ε approximation for k-connected subgraphs
- Parameterized Algorithms to Preserve Connectivity
- Improved approximation for tree augmentation: saving by rewiring
- Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
This page was built for publication: Approximation algorithms for vertex-connectivity augmentation on the cycle
