Tight Approximation Algorithm for Connectivity Augmentation Problems

DOI10.1007/11786986_39MaRDI QIDQ3613780zbMATH OpenOpenAlexFDO

Authors Guy Kortsarz, Zeev Nutov

Publication date 12 March 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11786986_39

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Tight approximation algorithm for connectivity augmentation problems
• Approximating connectivity augmentation problems
• Approximating connectivity augmentation problems
• Approximating Node-Connectivity Augmentation Problems
• Approximating node-connectivity augmentation problems

Cited in

(12)

• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• On the cycle augmentation problem: hardness and approximation algorithms
• Approximating node-connectivity augmentation problems
• Approximating connectivity augmentation problems
• Approximating connectivity augmentation problems
• NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems
• Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
• Approximating Node-Connectivity Augmentation Problems
• Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
• Improved approximation algorithms for min-cost connectivity augmentation problems
• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• Tight approximation algorithm for connectivity augmentation problems

This page was built for publication: Tight Approximation Algorithm for Connectivity Augmentation Problems

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