Approximating Steiner trees and forests with minimum number of Steiner points

DOI10.1007/978-3-319-18263-6_9zbMATH Open1460.68073OpenAlexW572952093MaRDI QIDQ3453286FDOQ3453286

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

Recommendations

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

zbMATH Keywords

approximation algorithmswireless networkSteiner 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

• 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
• A General Approximation Technique for Constrained Forest Problems
• Improved Approximation Algorithms for Uniform Connectivity Problems
• Steiner Tree Approximation via Iterative Randomized Rounding
• Approximations for Steiner trees with minimum number of Steiner points
• Relay placement for fault tolerance in wireless networks in higher dimensions
• Wireless network design via 3-decompositions
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Title not available (Why is that?)
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• Approximating Survivable Networks with Minimum Number of Steiner Points
• On better heuristics for Steiner minimum trees

Cited In (6)

• Minimum Steiner trees on a set of concyclic points and their center
• Narrow-Shallow-Low-Light Trees with and without Steiner Points
• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• IDENTIFYING STEINER MINIMAL TREES ON FOUR POINTS IN SPACE
• Title not available (Why is that?)
• Title not available (Why is that?)

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)