A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius
From MaRDI portal
Publication:3088090
DOI10.1007/978-3-642-22935-0_13zbMath1343.68311OpenAlexW2022694684MaRDI QIDQ3088090
Publication date: 17 August 2011
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_13
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)
Cites Work
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Covering a laminar family by leaf to leaf links
- On the integrality ratio for tree augmentation
- On the relationship between the biconnectivity augmentation and traveling salesman problems
- Approximating node connectivity problems via set covers
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- A \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from \(1\) to \(2\)
- Unnamed Item
This page was built for publication: A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius
