On the cycle augmentation problem: hardness and approximation algorithms
DOI10.1007/s00224-020-10025-6zbMath1473.05292OpenAlexW4232726547MaRDI QIDQ2230719
Fabrizio Grandoni, Krzysztof Sornat, Waldo Gálvez, Afrouz Jabal Ameli
Publication date: 28 September 2021
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-020-10025-6
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- A factor 2 approximation algorithm for the generalized Steiner network problem
- On the integrality ratio for tree augmentation
- Edge-connectivity augmentation problems
- The hardness of approximation: Gap location
- Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
- Approximating (unweighted) tree augmentation via lift-and-project. II
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- On the optimal vertex-connectivity augmentation
- The Design of Approximation Algorithms
- Augmenting Undirected Node-Connectivity by One
- Approximation Algorithms for Several Graph Augmentation Problems
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Approximation Algorithms for Graph Augmentation
- On Four-Connecting a Triconnected Graph
- LP-Relaxations for Tree Augmentation.
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- 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
- Parameterized Algorithms to Preserve Connectivity
- Improved approximation for tree augmentation: saving by rewiring
This page was built for publication: On the cycle augmentation problem: hardness and approximation algorithms
