Detail publikačního výsledku

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

ŠEDA, M.

Originální název

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

Anglický název

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

Druh

Stať ve sborníku v databázi WoS či Scopus

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.

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 v angličtině

Steiner tree, minimum spanning tree, Delaunay triangulation, heuristic

Autoři

ŠEDA, M.

Rok RIV

2011

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

Strany od

913

Strany počet

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",
  pages="6",
  publisher="Slovak University of Technology",
  address="Bratislava (Slovakia)",
  isbn="80-227-1995-1"
}