Approximating Steiner trees and forests with minimum number of Steiner points
From MaRDI portal
Publication:1796259
DOI10.1016/j.jcss.2018.08.001zbMath1397.05171OpenAlexW2885566559MaRDI QIDQ1796259
Publication date: 17 October 2018
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2018.08.001
Trees (05C05) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- Relay placement for fault tolerance in wireless networks in higher dimensions
- On better heuristics for Steiner minimum trees
- Wireless network design via 3-decompositions
- A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
- Low-degree minimum spanning trees
- An 11/6-approximation algorithm for the network Steiner problem
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Approximating Survivable Networks with Minimum Number of Steiner Points
- A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
- A General Approximation Technique for Constrained Forest Problems
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Improved Approximation Algorithms for Uniform Connectivity Problems
- Tighter Bounds for Graph Steiner Tree Approximation
- Steiner Tree Approximation via Iterative Randomized Rounding
- Approximations for Steiner trees with minimum number of Steiner points