A proof of the Gilbert-Pollak conjecture on the Steiner ratio
Copyright policy )A proof of the Gilbert-Pollak conjecture on the Steiner ratio
In [SIAM J. Appl. Math. 16, 1-29 (1968; Zbl 0159.22001)] \textit{E. N. Gilbert} and \textit{H. O. Pollak} conjectured that for any set \(P\) of \(n\) points of the Euclidean plane the following inequality holds between the lengths \(L_ s(P)\) and \(L_ m(P)\) of the Steiner minimum tree and the minimum spanning tree on \(P\), respectively: \(L_ s(P)\geq (\sqrt 3/2)L_ m(P)\). The inequality is proved in this paper.2 Editorial remark: As explained in [\textit{A. O. Ivanov} and \textit{A. A. Tuzhilin}, Algorithmica 62, No. 1--2, 630--632 (2012; Zbl 1239.05033)], the proof contains gaps, which means that the Steiner ratio Gilbert-Pollak conjecture is still open.
- Bell Labs United States
- College of New Jersey United States
- Academia Sinica Taiwan
- Institute of Applied Physics and Computational Mathematics China (People's Republic of)
- Center for Discrete Mathematics and Theoretical Computer Science United States
Gilbert-Pollak conjecture, spanning tree, Steiner minimum tree, Steiner ratio, Trees, hexagonal trees
Gilbert-Pollak conjecture, spanning tree, Steiner minimum tree, Steiner ratio, Trees, hexagonal trees
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).133 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!