A proof of the Gilbert-Pollak conjecture on the Steiner ratio |
| |
| Authors: | D. -Z. Du and F. K. Hwang |
| |
| Affiliation: | (1) Department of Computer Science, Princeton University, USA;(2) DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, USA;(3) Institute of Applied Mathematics, Academia Sinica, Beijing, China;(4) AT&T Bell Laboratories, 07974 Murray Hill, NJ, USA |
| |
| Abstract: | LetP be a set ofn points on the euclidean plane. LetLs(P) andLm(P) denote the lengths of the Steiner minimum tree and the minimum spanning tree onP, respectively. In 1968, Gilbert and Pollak conjectured that for anyP,Ls(P) ( 3/2)Lm(P). We provide a proof for their conjecture in this paper.supported by NSF under grant STC88-09648.supported in part by the National Natural Science Foundation of China. |
| |
| Keywords: | Steiner trees Spanning trees Steiner ratio Convexity Hexagonal trees |
| 本文献已被 SpringerLink 等数据库收录！ |
|
