| Issue |
RAIRO-Oper. Res.
Volume 35, Number 2, April June 2001
ROADEF'99
|
|
|---|---|---|
| Page(s) | 283 - 300 | |
| DOI | https://doi.org/10.1051/ro:2001115 | |
| Published online | 15 August 2002 | |
The triangles method to build X-trees from incomplete distance matrices
1
Institut Mathématique de Luminy, CNRS,
163 avenue de Luminy,
13009 Marseille, France;
guenoche@iml.univ-mrs.fr.
2
Centre d'Analyse et de Mathématiques Sociales,
École des Hautes Études en Sciences Sociales,
54 boulevard Raspail,
75270 Paris Cedex 06, France;
leclerc@ehess.fr.
Received:
May
1999
A method to infer X-trees (valued trees having X as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2n-3 distance values 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 generalized 2-tree spanning X.
Résumé
On décrit une méthode pour la reconstruction des X-arbres (arbres valués admettant X comme ensemble de feuilles) à partir de tableaux de distances incomplets (où certaines valeurs sont incertaines ou inconnues). Elle permet de construire un arbre non orienté à partir de 2n-3 valeurs de distance entre les n éléments de X, sous des conditions qui sont explicitées. Cette construction est basée sur une relation entre X-arbres et 2-arbres valués généralisés d'ensemble de sommets X.
Key words: X-tree / partial distances / 2-trees.
© EDP Sciences, 2001
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.