ISSN:
1432-0541
Keywords:
Steiner trees
;
Greed heuristic
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We disprove a conjecture of Shor and Smith on a greedy heuristic for the Steiner minimum tree by showing that the length ratio between the Steiner minimum tree and the greedy tree constructed by their method for the same set of points can be arbitrarily close to√3/2. We also propose a new conjecture.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01293486
Permalink