ISSN:
1432-0541
Keywords:
Graham's conjecture
;
Steiner trees
;
Spanning trees
;
Variational approach
;
Cocircular points
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Suppose a configurationX consists ofn points lying on a circle of radiusr. If at most one of the edges joining neighboring points has length strictly greater thanr, then the Steiner treeS consists of all these edges with a longest edge removed. In order to showS is, in fact, just the minimal spanning treeT, a variational approach is used to show the Steiner ratio for this configuration is at least one and equals one only ifS andT coincide. The variational approach greatly reduces the number of possible Steiner trees that need to be considered.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01758758
Permalink