2-node-connectivity network design
From MaRDI portal
Publication:2117701
DOI10.1007/978-3-030-80879-2_15OpenAlexW3183655254MaRDI QIDQ2117701
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/2002.04048
Related Items
Approximating \(k\)-connected \(m\)-dominating sets ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ On a partition LP relaxation for min-cost 2-node connected spanning subgraphs ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ A polylogarithmic approximation algorithm for 2-edge-connected dominating set ⋮ 2-node-connectivity network design ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle
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
- Covering a laminar family by leaf to leaf links
- On the integrality ratio for tree augmentation
- Coverings and structure of crossing families
- Approximation algorithms for connected dominating sets
- Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- A polylogarithmic approximation algorithm for 2-edge-connected dominating set
- Pruning 2-connected graphs
- Lower-Stretch Spanning Trees
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximation Algorithms for Graph Augmentation
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- 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
- Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
