Detail publikace
Insertion Heuristic for the Euclidean Steiner Tree Problem
ŠEDA, M. NEČAS, P.
Anglický název
Insertion Heuristic for the Euclidean Steiner Tree Problem
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, 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, the Steiner insertion heuristic is presented and computational results for benchmarks from OR-Library are discussed.
Klíčová slova anglicky
Steiner tree problem, Delaunay triangulation, heuristic
Rok RIV
2001
Vydáno
01.09.2001
Nakladatel
MARQ Ostrava
Místo
Ostrava
ISBN
80-85988-61-5
Kniha
Proceedings of the XXIIIrd International Colloquium Advanced Simulation of Systems ASIS 2001
Počet stran
6
BIBTEX
@inproceedings{BUT6634,
author="Miloš {Šeda} and Pavel {Nečas},
title="Insertion Heuristic for the Euclidean Steiner Tree Problem",
booktitle="Proceedings of the XXIIIrd International Colloquium Advanced Simulation of Systems ASIS 2001",
year="2001",
month="September",
publisher="MARQ Ostrava",
address="Ostrava",
isbn="80-85988-61-5"
}