Publication detail

Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation

ŠEDA, M.

Original Title

Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation

Type

journal article - other

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 being NP-hard, 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, approximation

Authors

ŠEDA, M.

RIV year

2005

Released

1. 7. 2005

ISBN

1109-2750

Periodical

WSEAS Transactions on Computers

Year of study

4

Number

6

State

Hellenic Republic

Pages from

471

Pages to

476

Pages count

6

BibTex

@article{BUT42793,
  author="Miloš {Šeda}",
  title="Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation",
  journal="WSEAS Transactions on Computers",
  year="2005",
  volume="4",
  number="6",
  pages="6",
  issn="1109-2750"
}