On the Cycle Augmentation Problem: hardness and approximation algorithms

DOI10.1007/978-3-030-39479-0_10MaRDI QIDQ2193089zbMATH OpenOpenAlexFDO

Authors Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Krzysztof Sornat

Publication date 24 August 2020

Full work available at URL https://doi.org/10.1007/978-3-030-39479-0_10

zbMATH Keywords

approximation algorithmscactus augmentationconnectivity augmentationcycle augmentation

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Recommendations

• On the cycle augmentation problem: hardness and approximation algorithms
• Approximation algorithms for vertex-connectivity augmentation on the cycle
• Approximation algorithms and hardness results for cycle packing problems
• Parameterized Approximability of the Disjoint Cycle Problem
• Approximation algorithms for cycle packing problems
• Computing and Combinatorics
• Approximation Algorithms for Min-Max Cycle Cover Problems
• Constant-factor approximations for cycle cover problems
• Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
• Complexity and algorithms for constant diameter augmentation problems

Cited in

(5)

• Approximation algorithms for connectivity augmentation problems
• Flexible Graph Connectivity
• Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
• Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
• Bridging the gap between tree and connectivity augmentation: unified and stronger approaches

This page was built for publication: On the Cycle Augmentation Problem: hardness and approximation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2193089)