On better heuristics for Steiner minimum trees

DOI10.1007/BF01581080zbMath0784.90094MaRDI QIDQ687085

Ding-Zhu Du, Yan-Jun Zhang

Publication date: 20 December 1993

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

zbMATH Keywords

Steiner minimum treeshortest networkapproximation performance ratiopolynomial-time heuristic

Mathematics Subject Classification ID

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

Related Items (4)

Approximating Steiner Trees and Forests with Minimum Number of Steiner Points ⋮ Combination algorithms for Steiner tree variants ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Local search for the Steiner tree problem in the Euclidean plane

Cites Work

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

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