Publication detail

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

ŠEDA, M.

Czech title

Heuristika pro řešení Steinerova problému v euklidovské rovině založená na Delaunayho triangulaci

English title

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

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

Czech abstract

Steinerův problém v euklidovské rovině spočívá v nalezení nejkratšího spojení dané množiny bodů v rovině. Řešení může zahrnovat i pomocné body, které původně zadány nebyly. Problem patří do třídy NP-těžkých problémů, a proto vyžaduje použití aproximativních nebo heuristických algoritmů, které zajistí provedení výpočtu v polynomiálním čase. V příspěvku je prezentována modifikace heuristiky postupného vkládání bodů a na testovacích příkladech z OR-Library je diskutována její efektivita.

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

Keywords in English

Steiner tree, minimum spanning tree, Delaunay triangulation, heuristic

RIV year

2004

Released

01.02.2004

Publisher

Slovak University of Technology

Location

Bratislava (Slovakia)

ISBN

80-227-1995-1

Book

Proceedings of the 3rd International Conference Aplimat

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",
  month="February",
  publisher="Slovak University of Technology",
  address="Bratislava (Slovakia)",
  isbn="80-227-1995-1"
}