Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-19T05:57:27.459Z Has data issue: false hasContentIssue false
  • English
  • Français

A note on tree realizations of matrices

Published online by Cambridge University Press:  11 October 2007

Alain Hertz  and
Sacha Varone
Alain Hertz
Affiliation:
Département de mathématiques et de génie industriel, École Polytechnique, Montréal, Canada; [email protected]
Sacha Varone
Affiliation:
Haute école de gestion de Genève, Économie d'Entreprise, Genève, Switzerland; [email protected]
Get access

Abstract

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 mij + mkl ≤ max{mik + mjl, mil + mjk} for all distinct i,j,k,l.

Keywords

Matricestree metrics4-point condition
Type
Research Article
Information
RAIRO - Operations Research , Volume 41 , Issue 4 , October 2007 , pp. 361 - 366
Copyright
© EDP Sciences, ROADEF, SMAI, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bandelt, H.-J., Recognition of tree metrics. SIAM J. Algebr. Discrete Methods 3 (1990) 1–6. CrossRef
J.-P. Barthélémy and A. Guénoche, Trees and proximity representations. John Wiley & Sons Ltd., Chichester (1991).
Buneman, P., A note on metric properties of trees. J. Combin. Theory Ser. B 17 (1974) 48–50. CrossRef
J.C. Culberson and P. Rudnicki, A fast algorithm for constructing trees from distance matrices. In Inf. Process. Lett. 30 (1989) 215–220.
Farach, M., Kannan, S. and Warnow, T., A robust model for finding optimal evolutionary trees. Algorithmica 13 (1995) 155–179. CrossRef
Floyd, R.W., Algorithm 97. Shortest path. Comm. ACM 5 (1962) 345. CrossRef
Hakimi, S.L. and Yau, S.S., Distance matrix of a graph and its realizability. Q. Appl. Math. 22 (1964) 305–317. CrossRef
Patrinos, A.N. and Hakimi, S.L., The distance matrix of a graph and its tree realization. Q. Appl. Math. 30 (1972) 255–269. CrossRef
Simões-Pereira, J.M.S., A note on the tree realizability of a distance matrix. J. Combin. Theory 6 (1969) 303–310. CrossRef
Varone, S.C., Trees related to realizations of distance matrices. Discrete Math. 192 (1998) 337–346. CrossRef