×

A fast algorithm for constructing trees from distance matrices. (English) Zbl 0665.68052

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.

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.)
PDFBibTeX XMLCite
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.