Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation

DOI10.1145/2700210zbMath1398.68255arXiv1304.6593OpenAlexW69311884MaRDI QIDQ4962187

Dániel Marx, László A. Végh

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.6593

zbMATH Keywords

fixed-parameter algorithmsconnectivity augmentation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (11)

On the tree augmentation problem ⋮ On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ On the fixed-parameter tractability of the maximum connectivity improvement problem ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Path-contractions, edge deletions and connectivity preservation ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ Minimum weight connectivity augmentation for planar straight-line graphs ⋮ Fast exact algorithms for survivable network design with uniform requirements ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle

This page was built for publication: Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation