Přístupnostní navigace
E-application
Search Search Close
Publication detail
ŠEDA, M.
Original Title
An Approximation for the Steiner Tree Problem in the Euclidean Plane
Type
conference paper
Language
English
Original Abstract
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.
Key words in English
Steiner tree, minimum spanning tree, Delaunay triangulation, heuristic
Authors
RIV year
2003
Released
1. 9. 2003
Publisher
Universitat Politecnica de Catalunya
Location
Barcelona (Spain)
ISBN
9958-617-18-8
Book
Proceedings of the 7th International Research/Expert Conference Trends in the Development of Machinery and Associated Technology TMT 2003
Pages from
1101
Pages to
1104
Pages count
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" }