Abstract | ||
---|---|---|
The long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal (spanning) tree is at least 32. This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. However, the proof for n = 4 by Pollak is sufficiently complicated that no generalization to any other value of n has been found. We use a different approach to give a very short proof for the n = 4 case. This approach also allows us to attack the n = 5 case, though the proof is no longer short (to be reported in a subsequent paper). |
Year | DOI | Venue |
---|---|---|
1982 | 10.1016/0097-3165(82)90056-5 | Journal of Combinatorial Theory, Series A |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Euclidean geometry,Conjecture,Mathematics | Journal | 32 |
Issue | ISSN | Citations |
3 | 0097-3165 | 14 |
PageRank | References | Authors |
15.66 | 1 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
D.-Z. Du | 1 | 219 | 52.53 |
E.Y Yao | 2 | 27 | 23.85 |
F. K. Hwang | 3 | 332 | 100.54 |