|
|||||
|
|
A proof of the Gilbert-Pollak conjecture on the Steiner ratio |
|
| Authors: | D. -Z. Du 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. LetL s(P) andL m (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,L s (P)≥(√3/2)L m (P). We provide a proof for their conjecture in this paper. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |