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"
}