From constrained to Unconstrained Maximum Agreement Subtree in Linear Time

Vincent Berry 1 Zeshan Peng 2, * Hing-Fung Ting 2
* Auteur correspondant
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We propose and study the Maximum Constrained Agreement Sub- tree (MCAST) problem, which is a variant of the classical Maximum Agreement Subtree (MAST) problem. Our problem allows users to ap- ply their domain knowledge to control the construction of the agreement subtrees in order to get better results. We show that the MCAST prob- lem can be reduced to the MAST problem in linear time and thus we have algorithms for MCAST with running times matching the fastest known algorithms for MAST.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2008, 50 (3), pp.369-385
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324070
Contributeur : Vincent Berry <>
Soumis le : mardi 23 septembre 2008 - 19:32:09
Dernière modification le : jeudi 11 janvier 2018 - 06:26:12
Document(s) archivé(s) le : vendredi 4 juin 2010 - 11:44:18

Fichiers

kmcast.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00324070, version 1

Collections

Citation

Vincent Berry, Zeshan Peng, Hing-Fung Ting. From constrained to Unconstrained Maximum Agreement Subtree in Linear Time. Algorithmica, Springer Verlag, 2008, 50 (3), pp.369-385. 〈lirmm-00324070〉

Partager

Métriques

Consultations de la notice

154

Téléchargements de fichiers

148