Metadata only
Date
1989Type
- Journal Article
ETH Bibliography
no
Altmetrics
Abstract
The Steiner ratio conjecture of Gilbert and Pollak states that for any set of n 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 √3/2. This is shown to be true for n = 3 by Gilbert and Pollak [SIAM J. Appl. Math., 16 (1968), pp. 1–29], for n = 4 by Pollak [J. Combin. Theory Ser. A, 24 (1978), pp. 278–295], and for n = 5 by Du, Hwang, and Yao [J. Combin. Theory Ser. A, 38 (1985), pp. 230–240]. In this paper a simple and powerful approach is used to prove the conjecture for n = 5 by arguing simultaneously with minimal spanning trees and Steiner minimal trees. Show more
Publication status
publishedExternal links
Journal / series
SIAM Journal on Applied MathematicsVolume
Pages / Article No.
Publisher
SIAMSubject
Steiner minimal tree; Steiner ratioOrganisational unit
03340 - Widmayer, Peter / Widmayer, Peter
More
Show all metadata
ETH Bibliography
no
Altmetrics