Detail publikace
An Approximation for the Steiner Tree Problem in the Euclidean Plane
ŠEDA, M.
Anglický název
An Approximation 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.
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
2003
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
Počet stran
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",
month="September",
publisher="Universitat Politecnica de Catalunya",
address="Barcelona (Spain)",
isbn="9958-617-18-8"
}