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