On the tree augmentation problem
From MaRDI portal
Publication:2659770
DOI10.1007/s00453-020-00765-9OpenAlexW2749954003MaRDI QIDQ2659770
Publication date: 26 March 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1703.07247
Related Items (6)
An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ 2-node-connectivity network design ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ Approximation algorithms for connectivity augmentation problems
Cites Work
- 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
- 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
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- Rational and integral \(k\)-regular matrices.
- Approximating (unweighted) tree augmentation via lift-and-project. II
- \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- Optimization with binet matrices
- Edmonds polytopes and a hierarchy of combinatorial problems
- Iterative Methods in Combinatorial Optimization
- Outline of an algorithm for integer solutions to linear programs
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximation Algorithms for Graph Augmentation
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- LP-Relaxations for Tree Augmentation.
- Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
- 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
- Improved approximation for tree augmentation: saving by rewiring
- Parameterized Algorithms
This page was built for publication: On the tree augmentation problem
