Detail publikačního výsledku

An Approximation for the Steiner Tree Problem in the Euclidean Plane

ŠEDA, M.

Originální název

An Approximation for the Steiner Tree Problem in the Euclidean Plane

Anglický název

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

Vydáno

01.09.2003

Nakladatel

Universitat Politecnica de Catalunya

Místo

Barcelona (Spain)

ISBN

9958-617-18-8

Kniha

Proceedings of the 7th International Research/Expert Conference Trends in the Development of Machinery and Associated Technology TMT 2003

Strany od

1101

Strany počet

4

BibTex

@inproceedings{BUT13220,
  author="Miloš {Šeda}",
  title="An Approximation for the Steiner Tree Problem in the Euclidean Plane",
  booktitle="Proceedings of the 7th International Research/Expert Conference Trends in the Development of Machinery and Associated Technology TMT 2003",
  year="2003",
  pages="4",
  publisher="Universitat Politecnica de Catalunya",
  address="Barcelona (Spain)",
  isbn="9958-617-18-8"
}