Publication detail
Heuristics for Steiner Tree Problem in the Euclidean Plane
ŠEDA, M.
Czech title
Heuristiky pro Steinerův problém v euklidovské rovině
English title
Heuristics for Steiner Tree Problem in the Euclidean Plane
Type
conference paper
Language
en
Czech abstract
Cílem Steinerova problému v euklidovské rovině je najít nejkratší síť spojující n bodů v rovině. Je známo, že řešení tohoto problému – Steinerův minimální strom – je kostrou na dané množině bodů a množině dalších pomocných bodů, které byly do roviny přidány tak, aby bylo zajištěno nalezení optima. Je známo, že problém je NP-úplný, a tedy pro velké instance musí být řešen aproximativními nebo heuristickými technikami. Příspěvek prezentuje hlavní přístupy a diskutuje jejich efektivitu.
Keywords in English
Voronoi diagram, Delaunay triangulation, heuristic
RIV year
2000
Released
01.09.2000
Publisher
MARQ Ostrava
Location
Sv. Hostýn - Bystřice pod Hostýnem
ISBN
80-85988-51-8
Book
XXIInd International Colloquium Advanced Simulation of Systems ASIS 2000
Pages from–to
91–96
Pages count
6
BIBTEX
@inproceedings{BUT1992,
author="Miloš {Šeda},
title="Heuristics for Steiner Tree Problem in the Euclidean Plane",
booktitle="XXIInd International Colloquium Advanced Simulation of Systems ASIS 2000",
year="2000",
month="September",
pages="91--96",
publisher="MARQ Ostrava",
address="Sv. Hostýn - Bystřice pod Hostýnem",
isbn="80-85988-51-8"
}