A DELAUNAY TRIANGULATION-BASED HEURISTIC FOR THE EUCLIDEAN STEINER PROBLEM

Authors
BEASLEY JE GOFFINET F
Citation
Je. Beasley et F. Goffinet, A DELAUNAY TRIANGULATION-BASED HEURISTIC FOR THE EUCLIDEAN STEINER PROBLEM, Networks, 24(4), 1994, pp. 215-224
Citations number
37
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
Networks → ACNP
ISSN journal
00283045
Volume
24
Issue
4
Year of publication
1994
Pages
215 - 224
Database
ISI
SICI code
0028-3045(1994)24:4<215:ADTHFT>2.0.ZU;2-5
Abstract
In this paper, we present a heuristic for the Euclidean Steiner proble m. The basis of this heuristic is to use the Delaunay triangulation to generate candidate Steiner vertices and then to remove redundant Stei ner vertices via the minimal spanning tree. This basic algorithm is in corporated into a simulated annealing framework. Computational results are given for a number of test problems drawn from the literature. (C ) 1994 John Wiley & Sons, Inc.