A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points

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

zbMATH Keywords

Steiner pointsSteiner tree

Mathematics Subject Classification ID

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