A Simple Proof of the Steiner Ratio Conjecture for Five Points
dc.contributor.author
Friedel, Jürgen
dc.contributor.author
Widmayer, Peter
dc.date.accessioned
2022-11-02T12:26:52Z
dc.date.available
2017-06-11T16:43:20Z
dc.date.available
2022-11-02T12:26:52Z
dc.date.issued
1989
dc.identifier.issn
0036-1399
dc.identifier.issn
1095-712X
dc.identifier.other
10.1137/0149057
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/99458
dc.description.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.
en_US
dc.language.iso
en
en_US
dc.publisher
SIAM
en_US
dc.subject
Steiner minimal tree
en_US
dc.subject
Steiner ratio
en_US
dc.title
A Simple Proof of the Steiner Ratio Conjecture for Five Points
en_US
dc.type
Journal Article
dc.date.published
2006-07-10
ethz.journal.title
SIAM Journal on Applied Mathematics
ethz.journal.volume
49
en_US
ethz.journal.issue
3
en_US
ethz.journal.abbreviated
SIAM J. Appl. Math.
ethz.pages.start
960
en_US
ethz.pages.end
967
en_US
ethz.identifier.nebis
000016405
ethz.publication.place
Philadelphia, PA
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter / Widmayer, Peter
en_US
ethz.date.deposited
2017-06-11T16:43:49Z
ethz.source
ECIT
ethz.identifier.importid
imp5936530b2d6b376091
ethz.ecitpid
pub:155602
ethz.eth
no
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2017-07-18T11:41:32Z
ethz.rosetta.lastUpdated
2023-02-07T07:29:08Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=A%20Simple%20Proof%20of%20the%20Steiner%20Ratio%20Conjecture%20for%20Five%20Points&rft.jtitle=SIAM%20Journal%20on%20Applied%20Mathematics&rft.date=1989&rft.volume=49&rft.issue=3&rft.spage=960&rft.epage=967&rft.issn=0036-1399&1095-712X&rft.au=Friedel,%20J%C3%BCrgen&Widmayer,%20Peter&rft.genre=article&rft_id=info:doi/10.1137/0149057&
Files in this item
| Files | Size | Format | Open in viewer |
|---|---|---|---|
|
There are no files associated with this item. |
|||
Publication type
-
Journal Article [120833]