On the extension of a partial metric to a tree metric

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.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (97kB)

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

Type:	Article de revue scientifique
Mots-clés ou Sujets:	tree, 2-tree, partial distance
Unité d'appartenance:	Faculté des sciences > Département d'informatique
Déposé par:	Vladimir Makarenkov
Date de dépôt:	23 mars 2016 13:14
Dernière modification:	20 avr. 2016 20:01
Adresse URL :	http://archipel.uqam.ca/id/eprint/8020

Modifier les métadonnées (propriétaire du document)

Statistiques