On optimal linear arrangements of trees (Q789395)

An optimal linear arrangement is a numbering of the vertices in a graph minimising the sum over the edges of the absolute values of the difference between the labels of the endpoints of the edge. For general graphs the problem of finding an optimal linear arrangement is known to be NP-complete. For trees an \(0(n^ 3)\) algorithm was improved to \(0(n^{2.2})\) by \textit{Y. Shiloach} [SIAM J. Comput. 8, 15-32 (1979; Zbl 0399.05021)]. The present authors improve this further to \(0(n^{1.6})\). The improvement is based on a far more refined analysis of algorithms like given by Shiloach (resulting into a simplified \(0(n^ 2)\) version), and a more intricate method of exploiting substructural information in the recursive calls, yielding the \(0(n^ c)\) bound with c approx. equal to log 3/log 2. The details are quite complicated - some of the lemmas are shown in the four page appendix to this 18 page paper.