Publication detail
Insertion Heuristic for the Euclidean Steiner Tree Problem
ŠEDA, M. NEČAS, P.
English title
Insertion Heuristic for the Euclidean Steiner Tree Problem
Type
conference paper
Language
en
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, the Steiner insertion heuristic is presented and computational results for benchmarks from OR-Library are discussed.
English 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, the Steiner insertion heuristic is presented and computational results for benchmarks from OR-Library are discussed.
Keywords in English
Steiner tree problem, Delaunay triangulation, heuristic
RIV year
2001
Released
01.09.2001
Publisher
MARQ Ostrava
Location
Ostrava
ISBN
80-85988-61-5
Book
Proceedings of the XXIIIrd International Colloquium Advanced Simulation of Systems ASIS 2001
Pages count
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"
}