Fiche du document
2004
- handle: 10670/1.weplk4
- Guénoche, Alain; Leclerc, Bruno et Makarenkov, Vladimir (2004). « On the extension of a partial metric to a tree metric ». Discrete Mathematics, 276(1-3), pp. 229-248.
Ce document est lié à :
http://archipel.uqam.ca/8020/
Ce document est lié à :
http://dx.doi.org/10.1016/S0012-365X(03)00294-2
Ce document est lié à :
doi:10.1016/S0012-365X(03)00294-2
Mots-clés
tree 2-tree partial distanceSujets proches
Plots (Diagrams) Graphs Diagrams, charts, etc Graphics Graphs Periodicity Natural cycles Cyclic theoryCiter ce document
Alain Guénoche et al., « On the extension of a partial metric to a tree metric », UQAM Archipel : articles scientifiques, ID : 10670/1.weplk4
Métriques
Partage / Export
Résumé
Farach, Kannan and Warnow (1995) have defined Problem MCA (matrix completion to additive) and proved it to be NP-complete: given a partial dissimilarity d on a finite set X, does there exist a tree metric extending d to all pairs of elements of X. We use a previously described simple method of phylogenetic reconstruction, and its extension to partial dissimilarities, to characterize some classes of polynomial instances of MCA and of a related problem. We point out that these problems admit many other polynomial instances. Our main tool consists of two classes of generalized cycles, together with the corresponding maximal acyclic graphs (2-trees and 2d-trees).