Detail publikace

Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation

ŠEDA, M.

Originální název

Solving the Euclidean Steiner Tree Problem Using Delaunay Triangulation

Typ

článek v časopise - ostatní, Jost

Jazyk

angličtina

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

Klíčová slova v angličtině

Steiner tree, minimum spanning tree, Delaunay triangulation, heuristic, approximation

Autoři

ŠEDA, M.

Rok RIV

2005

Vydáno

1. 7. 2005

ISSN

1109-2750

Periodikum

WSEAS Transactions on Computers

Ročník

4

Číslo

6

Stát

Řecká republika

Strany od

471

Strany do

476

Strany počet

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