On better heuristics for Steiner minimum trees

DOI10.1007/BF01581080zbMATH Open0784.90094MaRDI QIDQ687085FDOQ687085

Authors: Du Ding-Zhu, Yanjun Zhang 

Publication date: 20 December 1993

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

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

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)

Cites Work

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

Cited In (14)

• Approximating Steiner trees and forests with minimum number of Steiner points
• Approximating Steiner trees and forests with minimum number of Steiner points
• Improved computation of plane Steiner minimal trees
• Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study
• Title not available (Why is that?)
• 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
• Grade of service Steiner minimum trees in the Euclidean plane

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)