×

A note on tree realizations of matrices. (English) Zbl 1143.05314

Summary: It is well known that each tree metric \(M\) has a unique realization as a tree, and that this realization minimizes the total length of the edges among all other realizations of \(M\). We extend this result to the class of symmetric matrices \(M\) with zero diagonal, positive entries, and such that \(m_{ij}+m_{kl} \leq \max \{m_{ik}+m_{jl},m_{il}+m_{jk}\}\) for all distinct \(i,j,k,l\).

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
68R10 Graph theory (including graph drawing) in computer science
68U99 Computing methodologies and applications

Software:

Algorithm 97
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML Link

References:

[1] H.-J. Bandelt , Recognition of tree metrics . SIAM J. Algebr. Discrete Methods 3 ( 1990 ) 1 - 6 . Zbl 0687.05017 · Zbl 0687.05017 · doi:10.1137/0403001
[2] J.-P. Barthélémy and A. Guénoche , Trees and proximity representations . John Wiley & Sons Ltd., Chichester ( 1991 ). MR 1138723 | Zbl 0790.05021 · Zbl 0790.05021
[3] P. Buneman , A note on metric properties of trees . J. Combin. Theory Ser. B 17 ( 1974 ) 48 - 50 . Zbl 0286.05102 · Zbl 0286.05102 · doi:10.1016/0095-8956(74)90047-1
[4] J.C. Culberson and P. Rudnicki , A fast algorithm for constructing trees from distance matrices . In Inf. Process. Lett. 30 ( 1989 ) 215 - 220 . Zbl 0665.68052 · Zbl 0665.68052 · doi:10.1016/0020-0190(89)90216-0
[5] M. Farach , S. Kannan and T. Warnow , A robust model for finding optimal evolutionary trees . Algorithmica 13 ( 1995 ) 155 - 179 . Zbl 0831.92019 · Zbl 0831.92019 · doi:10.1007/BF01188585
[6] R.W. Floyd , Algorithm 97 . Shortest path. Comm. ACM 5 ( 1962 ) 345.
[7] S.L. Hakimi and S.S. Yau , Distance matrix of a graph and its realizability . Q. Appl. Math. 22 ( 1964 ) 305 - 317 . Zbl 0125.11804 · Zbl 0125.11804
[8] A.N. Patrinos and S.L. Hakimi , The distance matrix of a graph and its tree realization . Q. Appl. Math. 30 ( 1972 ) 255 - 269 . Zbl 0293.05103 · Zbl 0293.05103
[9] J.M.S. Simões-Pereira , A note on the tree realizability of a distance matrix . J. Combin. Theory 6 ( 1969 ) 303 - 310 . Zbl 0177.26903 · Zbl 0177.26903 · doi:10.1016/S0021-9800(69)80092-X
[10] S.C. Varone , Trees related to realizations of distance matrices . Discrete Math. 192 ( 1998 ) 337 - 346 . Zbl 0955.05070 · Zbl 0955.05070 · doi:10.1016/S0012-365X(98)00081-8
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.