Publication detail

Insertion Heuristic for the Euclidean Steiner Tree Problem

ŠEDA, M., NEČAS, P.

Original Title

Insertion Heuristic for the Euclidean Steiner Tree Problem

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, the Steiner insertion heuristic is presented and computational results for benchmarks from OR-Library are discussed.

Key words in English

Steiner tree problem, Delaunay triangulation, heuristic

Authors

ŠEDA, M., NEČAS, P.

RIV year

2001

Released

1. 9. 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 from

71

Pages to

76

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",
  pages="6",
  publisher="MARQ Ostrava",
  address="Ostrava",
  isbn="80-85988-61-5"
}