A note on tree realizations of matrices

Alain Hertz; Sacha Varone

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 4, page 361-366
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Hertz, Alain, and Varone, Sacha. "A note on tree realizations of matrices." RAIRO - Operations Research 41.4 (2007): 361-366. <http://eudml.org/doc/250136>.

@article{Hertz2007,
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. },
author = {Hertz, Alain, Varone, Sacha},
journal = {RAIRO - Operations Research},
keywords = {Matrices; tree metrics; 4-point condition; matrices},
language = {eng},
month = {10},
number = {4},
pages = {361-366},
publisher = {EDP Sciences},
title = {A note on tree realizations of matrices},
url = {http://eudml.org/doc/250136},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Hertz, Alain
AU - Varone, Sacha
TI - A note on tree realizations of matrices
JO - RAIRO - Operations Research
DA - 2007/10//
PB - EDP Sciences
VL - 41
IS - 4
SP - 361
EP - 366
AB - 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.
LA - eng
KW - Matrices; tree metrics; 4-point condition; matrices
UR - http://eudml.org/doc/250136
ER -

References

top
  1. H.-J. Bandelt, Recognition of tree metrics. SIAM J. Algebr. Discrete Methods3 (1990) 1–6.  
  2. J.-P. Barthélémy and A. Guénoche, Trees and proximity representations. John Wiley & Sons Ltd., Chichester (1991).  
  3. P. Buneman, A note on metric properties of trees. J. Combin. Theory Ser. B17 (1974) 48–50.  
  4. J.C. Culberson and P. Rudnicki, A fast algorithm for constructing trees from distance matrices. In Inf. Process. Lett.30 (1989) 215–220.  
  5. M. Farach, S. Kannan and T. Warnow, A robust model for finding optimal evolutionary trees. Algorithmica13 (1995) 155–179.  
  6. R.W. Floyd, Algorithm 97. Shortest path. Comm. ACM5 (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.  
  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.  
  9. J.M.S. Simões-Pereira, A note on the tree realizability of a distance matrix. J. Combin. Theory6 (1969) 303–310.  
  10. S.C. Varone, Trees related to realizations of distance matrices. Discrete Math.192 (1998) 337–346.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.