A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
From MaRDI portal
Publication:1607061
DOI10.1016/S0020-0190(00)00095-8zbMath1003.68206OpenAlexW2087989351MaRDI QIDQ1607061
Alexander Z. Zelikovsky, Ion I. Măndoiu
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(00)00095-8
Trees (05C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (11)
Improved approximation algorithms for single-tiered relay placement ⋮ Approximating Steiner Trees and Forests with Minimum Number of Steiner Points ⋮ (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs ⋮ Relay placement for fault tolerance in wireless networks in higher dimensions ⋮ The subdivision-constrained routing requests problem ⋮ Combination algorithms for Steiner tree variants ⋮ Wireless network design via 3-decompositions ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Algorithms for connected set cover problem and fault-tolerant connected set cover problem ⋮ Relay placement for two-connectivity ⋮ An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane
Cites Work
- Steiner tree problem with minimum number of Steiner points and bounded edge-length
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- Low-degree minimum spanning trees
- An 11/6-approximation algorithm for the network Steiner problem
- A threshold of ln n for approximating set cover
- Improved Approximations for the Steiner Tree Problem
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Bottleneck Steiner trees in the plane
- Approximations for Steiner trees with minimum number of Steiner points
This page was built for publication: A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
