Publication result detail

Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation

ŠEDA, M.

Original Title

Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation

English Title

Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation

Type

Peer-reviewed article not indexed in WoS or Scopus

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.

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 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.

Released

01.07.2005

ISBN

1109-2750

Periodical

WSEAS Transactions on Computers

Volume

4

Number

6

State

Hellenic Republic

Pages from

471

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