Graham's problem on shortest networks for points on a circle |
| |
Authors: | J H Rubinstein and D A Thomas |
| |
Affiliation: | (1) Institute of Advanced Study, and Mathematics Department, University of Melbourne, 3052 Parkville, Victoria, Australia;(2) University of Melbourne, 3052 Parkville, Victoria, Australia |
| |
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. |
| |
Keywords: | Graham's conjecture Steiner trees Spanning trees Variational approach Cocircular points |
本文献已被 SpringerLink 等数据库收录! |
|