Detail publikačního výsledku

Insertion Heuristic for the Euclidean Steiner Tree Problem

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

Originální název

Insertion Heuristic for the Euclidean Steiner Tree Problem

Anglický název

Insertion Heuristic for the Euclidean Steiner Tree Problem

Druh

Stať ve sborníku v databázi WoS či Scopus

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 v angličtině

Steiner tree problem, Delaunay triangulation, heuristic

Autoři

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

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

Strany od

71

Strany počet

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