Publication detail
A Delaunay Triangulation-Based Heuristic for the Steiner Tree Problem in the Euclidean Plane
ŠEDA, M.
Czech title
Heuristika pro řešení Steinerova problému v euklidovské rovině založená na Delaunayho triangulaci
English title
A Delaunay Triangulation-Based Heuristic for the Steiner Tree Problem in the Euclidean Plane
Type
conference paper
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 is NP-hard, so 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
Steinerův problém v euklidovské rovině spočívá v nalezení nejkratšího spojení dané množiny bodů v rovině. Řešení může zahrnovat i pomocné body, které původně zadány nebyly. Problem patří do třídy NP-těžkých problémů, a proto vyžaduje použití aproximativních nebo heuristických algoritmů, které zajistí provedení výpočtu v polynomiálním čase. V příspěvku je prezentována modifikace heuristiky postupného vkládání bodů a na testovacích příkladech z OR-Library je diskutována její efektivita.
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 is NP-hard, so 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
RIV year
2004
Released
01.02.2004
Publisher
Slovak University of Technology
Location
Bratislava (Slovakia)
ISBN
80-227-1995-1
Book
Proceedings of the 3rd International Conference Aplimat
Pages count
6
BIBTEX
@inproceedings{BUT12868,
author="Miloš {Šeda},
title="A Delaunay Triangulation-Based Heuristic for the Steiner Tree Problem in the Euclidean Plane",
booktitle="Proceedings of the 3rd International Conference Aplimat",
year="2004",
month="February",
publisher="Slovak University of Technology",
address="Bratislava (Slovakia)",
isbn="80-227-1995-1"
}