Approximating Steiner Trees and Forests with Minimum Number of Steiner Points

DOI10.1007/978-3-319-18263-6_9zbMath1460.68073OpenAlexW572952093MaRDI QIDQ3453286

Nachshon Cohen, Zeev Nutov

Publication date: 20 November 2015

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-18263-6_9

zbMATH Keywords

wireless networkapproximation algorithmsSteiner treeSteiner forest2-connectivityunit-disc graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)

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
• Approximating Survivable Networks with Minimum Number of Steiner Points
• A General Approximation Technique for Constrained Forest Problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Improved Approximation Algorithms for Uniform Connectivity Problems
• Steiner Tree Approximation via Iterative Randomized Rounding
• Approximations for Steiner trees with minimum number of Steiner points