Publication detail

A Delaunay Triangulation-Based Heuristic for the Steiner Tree Problem in the Euclidean Plane

ŠEDA, M.

Original Title

A Delaunay Triangulation-Based Heuristic for the Steiner Tree Problem in the Euclidean Plane

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

Key words in English

Steiner tree, minimum spanning tree, Delaunay triangulation, heuristic

Authors

ŠEDA, M.

RIV year

2004

Released

1. 2. 2004

Publisher

Slovak University of Technology

Location

Bratislava (Slovakia)

ISBN

80-227-1995-1

Book

Proceedings of the 3rd International Conference Aplimat

Pages from

913

Pages to

918

Pages count

6

BibTex

@inproceedings{BUT12868,
  author="Miloš {Šeda}",
  title="A Delaunay Triangulation-Based Heuristic for the Steiner Tree Problem in the Euclidean Plane",
  booktitle="Proceedings of the 3rd International Conference Aplimat",
  year="2004",
  pages="6",
  publisher="Slovak University of Technology",
  address="Bratislava (Slovakia)",
  isbn="80-227-1995-1"
}