LP-relaxations for tree augmentation
From MaRDI portal
Publication:1706120
DOI10.1016/j.dam.2017.12.033zbMath1382.05016OpenAlexW2791470040MaRDI QIDQ1706120
Publication date: 21 March 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6636/
Trees (05C05) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Flexible Graph Connectivity, A simple LP-based approximation algorithm for the matching augmentation problem, Node connectivity augmentation via iterative randomized rounding, Approximation algorithms for vertex-connectivity augmentation on the cycle, Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem, Flexible graph connectivity
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
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- 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 (unweighted) tree augmentation via lift-and-project. II
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- A primal-dual approximation algorithm for generalized Steiner network problems
- Iterative Methods in Combinatorial Optimization
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximation Algorithms for Graph Augmentation
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- 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
