Detail publikace

Heuristika pro řešení Steinerova problému v euklidovské rovině založená na Delaunayho triangulaci

ŠEDA, M.

Český název

Heuristika pro řešení Steinerova problému v euklidovské rovině založená na Delaunayho triangulaci

Anglický název

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

Typ

článek ve sborníku ve WoS nebo Scopus

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 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.

Český abstrakt

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.

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 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.

Klíčová slova anglicky

Steiner tree, minimum spanning tree, Delaunay triangulation, heuristic

Rok RIV

2004

Vydáno

01.02.2004

Nakladatel

Slovak University of Technology

Místo

Bratislava (Slovakia)

ISBN

80-227-1995-1

Kniha

Proceedings of the 3rd International Conference Aplimat

Počet stran

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