Detail publikace
Řešení euklidovského Steinerova problému s využitím Delaunayho triangulace
ŠEDA, M.
Český název
Řešení euklidovského Steinerova problému s využitím Delaunayho triangulace
Anglický název
Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation
Typ
článek v časopise - ostatní, Jost
Jazyk
en
Originální abstrakt
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.
Český abstrakt
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.
Anglický abstrakt
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.
Klíčová slova anglicky
Steiner tree, minimum spanning tree, Delaunay triangulation, heuristic, approximation
Rok RIV
2005
Vydáno
01.07.2005
ISSN
1109-2750
Časopis
WSEAS Transactions on Computers
Ročník
4
Číslo
6
Počet stran
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"
}