Document RAIRO Oper. Res. 41 (2007) 361-366
DOI: 10.1051/ro:2007028
A note on tree realizations of matrices
Alain Hertz1 and Sacha Varone21 Département de mathématiques et de génie industriel, École Polytechnique, Montréal, Canada; alain.hertz@gerad.ca
2 Haute école de gestion de Genève, Économie d'Entreprise, Genève, Switzerland; sacha.varone@hesge.ch
(Received March 07, 2005. Accepted January 19, 2007. Published online 11 October 2007.)
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
for all distinct i,j,k,l.
Mathematics Subject Classification. 05C50, 05B20, 68R10, 68U99
Key words: Matrices, tree metrics, 4-point condition
© EDP Sciences, ROADEF, SMAI 2007