ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

Graham's problem on shortest networks for points on a circle (1992)

Rubinstein, J. H. ; Thomas, D. A.

Springer

Algorithmica 7 (1992), S. 193-218

add to mindlist on the mindlist

Details

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

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit