A proof of the Gilbert-Pollak conjecture on the Steiner ratio (Q1186792)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A proof of the Gilbert-Pollak conjecture on the Steiner ratio |
scientific article |
Statements
A proof of the Gilbert-Pollak conjecture on the Steiner ratio (English)
0 references
28 June 1992
0 references
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.
0 references
Gilbert-Pollak conjecture
0 references
Steiner ratio
0 references
hexagonal trees
0 references
Steiner minimum tree
0 references
spanning tree
0 references