AN O(N-2) HEURISTIC FOR STEINER MINIMAL-TREES IN E(3)

Authors
SMITH JM WEISS R PATEL M
Citation
Jm. Smith et al., AN O(N-2) HEURISTIC FOR STEINER MINIMAL-TREES IN E(3), Networks, 26(4), 1995, pp. 273-289
Citations number
35
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
Networks → ACNP
ISSN journal
00283045
Volume
26
Issue
4
Year of publication
1995
Pages
273 - 289
Database
ISI
SICI code
0028-3045(1995)26:4<273:AOHFSM>2.0.ZU;2-E
Abstract
Even though the problem of computing Steiner minimal trees (SMTs) in t he plane is well known to be NP-hard, there exist heuristic algorithms which run in polynomial time. Recent research results have shown that the problem in three dimensions is demonstrably more difficult. This paper approaches the development of a heuristic for the problem utiliz ing the Delaunay triangulation in 3-space to compute suboptimal SMTs. Computational results are also provided. (C) 1995 John Wiley & Sons, I nc.