A Delaunay Triangulation-Based Heuristic for the Steiner Tree Problem in the Euclidean Plane

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F04%3APU47004" target="_blank" >RIV/00216305:26210/04:PU47004 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
A Delaunay Triangulation-Based Heuristic for the Steiner Tree Problem in the Euclidean Plane
Original language description
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 name
Heuristika pro řešení Steinerova problému v euklidovské rovině založená na Delaunayho triangulaci
Czech description
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.

Publication year
2004
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 3rd International Conference Aplimat
ISBN
80-227-1995-1
ISSN
—
e-ISSN
—
Number of pages
6
Pages from-to
913-918
Publisher name
Slovak University of Technology
Place of publication
Bratislava (Slovakia)
Event location
Bratislava
Event date
Feb 3, 2004
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)