On better heuristics for Steiner minimum trees

DOI10.1007/BF01581080MaRDI QIDQ687085zbMATH OpenFDO

Authors Du Ding-Zhu, Yanjun Zhang

Publication date 20 December 1993

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

shortest networkSteiner minimum treeapproximation performance ratiopolynomial-time heuristic

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On greedy heuristic for Steiner minimum trees
• Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study
• Improved Computation of Optimal Rectilinear Steiner Minimal Trees
• An improved algorithm for computing Steiner minimal trees in Euclidean d-space
• Euclidean Steiner minimum trees: An improved exact algorithm
• Improved Approximations for the Steiner Tree Problem
• scientific article; zbMATH DE number 742979
• Improved computation of plane Steiner minimal trees
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• scientific article; zbMATH DE number 1834686

Cites work

• scientific article; zbMATH DE number 3912403 (Why is no real title available?)
• scientific article; zbMATH DE number 3520428 (Why is no real title available?)
• A Lower Bound for the Steiner Tree Problem
• A New Bound for the Steiner Ratio
• An 11/6-approximation algorithm for the network Steiner problem
• Comments on Bern's probabilistic results on rectilinear Steiner trees
• On Steiner Minimal Trees with Rectilinear Distance
• Some remarks on the Steiner problem
• Steiner Minimal Trees
• The Complexity of Computing Steiner Minimal Trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Steiner problem in phylogeny is NP-complete
• The Steiner ratio conjecture for six points

Cited in

(14)

• Grade of service Steiner minimum trees in the Euclidean plane
• Approximating Steiner trees and forests with minimum number of Steiner points
• Improved computation of plane Steiner minimal trees
• Approximating Steiner trees and forests with minimum number of Steiner points
• Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study
• scientific article; zbMATH DE number 3918122 (Why is no real title available?)
• On greedy heuristic for Steiner minimum trees
• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• Unexplored Steiner ratios in geometric networks
• On shortest two-connected Steiner networks with Euclidean distance
• A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space
• Local search for the Steiner tree problem in the Euclidean plane
• A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem
• Combination algorithms for Steiner tree variants

This page was built for publication: On better heuristics for Steiner minimum trees

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