Approximating Steiner trees and forests with minimum number of Steiner points

DOI10.1007/978-3-319-18263-6_9MaRDI QIDQ3453286zbMATH OpenOpenAlexFDO

Authors 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

2-connectivityapproximation algorithmsSteiner forestSteiner treeunit-disc graphwireless network

Mathematics Subject Classification ID

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

Recommendations

• Approximating Steiner trees and forests with minimum number of Steiner points
• scientific article; zbMATH DE number 1796993
• Approximating minimum Steiner point trees in Minkowski planes

Cites work

• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• A General Approximation Technique for Constrained Forest Problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• An 11/6-approximation algorithm for the network Steiner problem
• Approximations for Steiner trees with minimum number of Steiner points
• scientific article; zbMATH DE number 3633251 (Why is no real title available?)
• Improved Approximation Algorithms for Uniform Connectivity Problems
• Low-degree minimum spanning trees
• On better heuristics for Steiner minimum trees
• Relay placement for fault tolerance in wireless networks in higher dimensions
• Steiner tree approximation via iterative randomized rounding
• Wireless network design via 3-decompositions

Cited in

(7)

• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• Approximating Steiner trees and forests with minimum number of Steiner points
• scientific article; zbMATH DE number 5629898 (Why is no real title available?)
• IDENTIFYING STEINER MINIMAL TREES ON FOUR POINTS IN SPACE
• scientific article; zbMATH DE number 1099658 (Why is no real title available?)
• Narrow-Shallow-Low-Light Trees with and without Steiner Points
• Minimum Steiner trees on a set of concyclic points and their center

This page was built for publication: Approximating Steiner trees and forests with minimum number of Steiner points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453286)