Approximating connectivity augmentation problems
DOI10.1145/1644015.1644020zbMATH Open1300.68067OpenAlexW2621727216MaRDI QIDQ2930278FDOQ2930278
Publication date: 18 November 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1644015.1644020
approximation algorithmshardness of approximationconnectivity augmentationnode-connectivityelement-connectivity
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Connectivity (05C40)
Cited In (16)
- On algebraic connectivity augmentation
- Node connectivity augmentation via iterative randomized rounding
- Augmenting edge-connectivity between vertex subsets
- A note on the vertex-connectivity augmentation problem
- Approximating node-connectivity augmentation problems
- The Generalized Terminal Backup Problem
- Hypergraph connectivity augmentation
- Approximation algorithms for connectivity augmentation problems
- Approximation algorithms for node and element connectivity augmentation problems
- Minimum Cardinality Point-to-point Connectivity Augmentation Problem
- Title not available (Why is that?)
- Approximating connectivity augmentation problems
- Primal-dual approach for directed vertex connectivity augmentation and generalizations
- Approximating Minimum Cost Connectivity Orientation and Augmentation
- Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
- Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
This page was built for publication: Approximating connectivity augmentation problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2930278)
