It is well known that each tree metric has a unique realization as a tree, and that this realization minimizes the total length of the edges among all other realizations of . We extend this result to the class of symmetric matrices with zero diagonal, positive entries, and such that for all distinct .
Mots-clés : matrices, tree metrics, 4-point condition
@article{RO_2007__41_4_361_0, author = {Hertz, Alain and Varone, Sacha}, title = {A note on tree realizations of matrices}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {361--366}, publisher = {EDP-Sciences}, volume = {41}, number = {4}, year = {2007}, doi = {10.1051/ro:2007028}, mrnumber = {2361290}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro:2007028/} }
TY - JOUR AU - Hertz, Alain AU - Varone, Sacha TI - A note on tree realizations of matrices JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2007 SP - 361 EP - 366 VL - 41 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2007028/ DO - 10.1051/ro:2007028 LA - en ID - RO_2007__41_4_361_0 ER -
%0 Journal Article %A Hertz, Alain %A Varone, Sacha %T A note on tree realizations of matrices %J RAIRO - Operations Research - Recherche Opérationnelle %D 2007 %P 361-366 %V 41 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2007028/ %R 10.1051/ro:2007028 %G en %F RO_2007__41_4_361_0
Hertz, Alain; Varone, Sacha. A note on tree realizations of matrices. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 4, pp. 361-366. doi : 10.1051/ro:2007028. http://www.numdam.org/articles/10.1051/ro:2007028/
[1] Recognition of tree metrics. SIAM J. Algebr. Discrete Methods 3 (1990) 1-6. | Zbl
,[2] Trees and proximity representations. John Wiley & Sons Ltd., Chichester (1991). | MR | Zbl
and ,[3] A note on metric properties of trees. J. Combin. Theory Ser. B 17 (1974) 48-50. | Zbl
,[4] A fast algorithm for constructing trees from distance matrices. In Inf. Process. Lett. 30 (1989) 215-220. | Zbl
and ,[5] A robust model for finding optimal evolutionary trees. Algorithmica 13 (1995) 155-179. | Zbl
, and ,[6] Algorithm 97. Shortest path. Comm. ACM 5 (1962) 345.
,[7] Distance matrix of a graph and its realizability. Q. Appl. Math. 22 (1964) 305-317. | Zbl
and ,[8] The distance matrix of a graph and its tree realization. Q. Appl. Math. 30 (1972) 255-269. | Zbl
and ,[9] A note on the tree realizability of a distance matrix. J. Combin. Theory 6 (1969) 303-310. | Zbl
,[10] Trees related to realizations of distance matrices. Discrete Math. 192 (1998) 337-346. | Zbl
,Cité par Sources :