Publication detail
Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation
ŠEDA, M.
Czech title
Řešení euklidovského Steinerova problému s využitím Delaunayho triangulace
English title
Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation
Type
journal article - other
Language
en
Original abstract
The Euclidean Steiner Tree Problem is to find a shortest network spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set. The problem being NP-hard, polynomial-time approximations or heuristics are desired. In this paper, a modification of the Steiner insertion heuristic is presented and computational results for benchmarks from OR-Library are discussed.
Czech abstract
Cílem Steinerova problému v euklidovské rovině je najít nejkratší spojení množiny bodů v rovině, přičemž některé hrany minimálního Steinerova stromu, který je řešením problému, mohou jako koncové body mít i body, které nebyly zadány. Steinerův problém patří mezi NP-těžké problémy, proto je nutné jej řešit heuristickými nebo aproximativními metodami. V příspěvku je prezentována modifikace deterministické heuristiky vkládání pomocných bodů využívající Delaunayho triangulaci a jsou diskutovány výsledky výpočtů pro testovací úlohy z OR-Library.
English abstract
The Euclidean Steiner Tree Problem is to find a shortest network spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set. The problem being NP-hard, polynomial-time approximations or heuristics are desired. In this paper, a modification of the Steiner insertion heuristic is presented and computational results for benchmarks from OR-Library are discussed.
Keywords in English
Steiner tree, minimum spanning tree, Delaunay triangulation, heuristic, approximation
RIV year
2005
Released
01.07.2005
ISSN
1109-2750
Journal
WSEAS Transactions on Computers
Volume
4
Number
6
Pages count
6
BIBTEX
@article{BUT42793,
author="Miloš {Šeda},
title="Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation",
journal="WSEAS Transactions on Computers",
year="2005",
volume="4",
number="6",
month="July",
issn="1109-2750"
}