Abstract.
We present a class of O(n log n) heuristics for the Steiner tree problem in the Euclidean plane. These heuristics identify a small number of subsets with few, geometrically close, terminals using minimum spanning trees and other well-known structures from computational geometry: Delaunay triangulations, Gabriel graphs, relative neighborhood graphs, and higher-order Voronoi diagrams. Full Steiner trees of all these subsets are sorted according to some appropriately chosen measure of quality. A tree spanning all terminals is constructed using greedy concatenation. New heuristics are compared with each other and with heuristics from the literature by performing extensive computational experiments on both randomly generated and library problem instances.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received October 27, 1997; revised May 7, 1998.
Rights and permissions
About this article
Cite this article
Zachariasen, M., Winter, P. Concatenation-Based Greedy Heuristics for the Euclidean Steiner Tree Problem. Algorithmica 25, 418–437 (1999). https://doi.org/10.1007/PL00009287
Issue Date:
DOI: https://doi.org/10.1007/PL00009287