Concatenation-Based Greedy Heuristic for the Euclidean Steiner Tree Problem

Martin Zachariasen, Pawel Winter

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

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.
OriginalsprogEngelsk
TidsskriftAlgorithmica
Vol/bind25
Sider (fra-til)418-437
ISSN0178-4617
StatusUdgivet - 1999
Udgivet eksterntJa

Emneord

  • Steiner Tree Problem
  • Euclidean Plane
  • Heuristics
  • Computational Geometry
  • Minimum Spanning Trees
  • Delaunay Triangulations

Fingeraftryk

Dyk ned i forskningsemnerne om 'Concatenation-Based Greedy Heuristic for the Euclidean Steiner Tree Problem'. Sammen danner de et unikt fingeraftryk.

Citationsformater