The triangles method to build X-trees from incomplete distance matrices

Authors
Guenoche, A Leclerc, B
Citation
A. Guenoche et B. Leclerc, The triangles method to build X-trees from incomplete distance matrices, RAIRO RE OP, 35(2), 2001, pp. 283-300
Citations number
22
Categorie Soggetti
Engineering Mathematics
Journal title
RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH
ISSN journal
03990559 → ACNP
Volume
35
Issue
2
Year of publication
2001
Pages
283 - 300
Database
ISI
SICI code
0399-0559(200104/06)35:2<283:TTMTBX>2.0.ZU;2-H
Abstract
A method to infer X-trees (valued trees having X as set of leaves) from inc omplete distance arrays (where some entries are uncertain or unknown) is de scribed. It allows us to build an unrooted tree using only 2n-3 distance va lues between the n elements of X, if they fulfill some explicit conditions. This construction is based on the mapping between X-tree and a weighted ge neralized 2-tree spanning X.