scientific article; zbMATH DE number 7205039
From MaRDI portal
Publication:5111750
DOI10.4230/LIPICS.ESA.2017.61zbMATH Open1442.68181MaRDI QIDQ5111750FDOQ5111750
Publication date: 27 May 2020
Title of this publication is not available (Why is that?)
Recommendations
- On the tree augmentation problem
- Almost optimal algorithms for diameter-optimally augmenting trees
- Almost optimal algorithms for diameter-optimally augmenting trees
- Algorithms for radius-optimally augmenting trees in a metric space
- Algorithms for radius-optimally augmenting trees in a metric space
- Shortest augmenting paths for online matchings on trees
- A tight bound for shortest augmenting paths on trees
- Augmenting trees to meet biconnectivity and diameter constraints
- LP-relaxations for tree augmentation
- LP-relaxations for tree augmentation
approximation algorithmintegrality gaptree augmentationhalf-integral extreme pointslogarithmic costs
Linear programming (90C05) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Cites Work
- Title not available (Why is that?)
- Parameterized Algorithms
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation
- Iterative Methods in Combinatorial Optimization
- On the integrality ratio for tree augmentation
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- A \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from \(1\) to \(2\)
- A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- Title not available (Why is that?)
- Covering a laminar family by leaf to leaf links
- Approximation Algorithms for Graph Augmentation
- Approximation Algorithms for Several Graph Augmentation Problems
- Title not available (Why is that?)
- Approximating (unweighted) tree augmentation via lift-and-project. II
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- LP-Relaxations for Tree Augmentation.
Cited In (12)
- Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
- A technique for obtaining true approximations for \(k\)-center with covering constraints
- Flexible graph connectivity
- Node connectivity augmentation via iterative randomized rounding
- Mixed covering of trees and the augmentation problem with odd diameter constraints
- A Technique for Obtaining True Approximations for k-Center with Covering Constraints
- Flexible Graph Connectivity
- A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
- LP-relaxations for tree augmentation
- 2-node-connectivity network design
- Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
- On the cycle augmentation problem: hardness and approximation algorithms
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111750)
