Culberson, Joseph C.; Rudnicki, Piotr A fast algorithm for constructing trees from distance matrices. (English) Zbl 0665.68052 Inf. Process. Lett. 30, No. 4, 215-220 (1989). We present an algorithm which, given a tree-realizable distance matrix, constructs the tree in optimal \(O(n^ 2)\) time. For trees of bounded degree k, the algorithm runs in O(k n \(log_ k n)\) time, and for random trees it apparently runs in O(n) average time. We show how the algorithm can be used to test tree-realizability of a distance matrix. Cited in 1 ReviewCited in 28 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) Keywords:random trees; tree-realizability; distance matrix PDFBibTeX XMLCite \textit{J. C. Culberson} and \textit{P. Rudnicki}, Inf. Process. Lett. 30, No. 4, 215--220 (1989; Zbl 0665.68052) Full Text: DOI References: [1] Boesch, F. T., Properties of the distance matrix of a tree, Q. Appl. Math., 26, 607-609 (1968) · Zbl 0167.52205 [2] Chaiken, S.; Dewdney, A. K.; Slater, P. J., An optimal diagonal tree code, SIAM J. Algebraic Discrete Methods, 4, 1, 42-49 (1983) · Zbl 0512.05023 [3] Hakimi, S. L.; Yau, S. S., Distance matrix of a graph and its realizability, Q. Appl. Math., 22, 305-317 (1964) · Zbl 0125.11804 [4] Palmer, E. M., Wiley-Interscience Series in Discrete Mathematics, (Graphical Evolution (1985), Wiley: Wiley New York) [5] Patrinos, A. N.; Hakimi, S. L., The distance matrix of a graph and its tree realization, Q. Appl. Math., 30, 255-269 (1972) · Zbl 0293.05103 [6] Simões-Pereira, J. M.S.; Zamfirescu, C. M., Submatrices of non-tree-realizable distance matrices, Linear Algebra Appl., 44, 1-17 (1982) · Zbl 0483.05045 [7] Zaretskiiǐ, K. A., Postroenie dereva po naboru rasstoianiǐ mezhdu visiatchimi vershinami, Uspehki Mat. Nauk, 20, 6, 90-92 (1965) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.