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
    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
    0 references
    0 references

    Identifiers