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"
}