From constrained to Unconstrained Maximum Agreement Subtree in Linear Time - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Algorithmica Année : 2008

From constrained to Unconstrained Maximum Agreement Subtree in Linear Time

Résumé

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.
Fichier principal
Vignette du fichier
kmcast.pdf (199.36 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00324070 , version 1 (23-09-2008)

Identifiants

Citer

Vincent Berry, Zeshan S. Peng, Hing-Fung Ting. From constrained to Unconstrained Maximum Agreement Subtree in Linear Time. Algorithmica, 2008, 50 (3), pp.369-385. ⟨10.1007/s00453-007-9084-8⟩. ⟨lirmm-00324070⟩
147 Consultations
399 Téléchargements

Altmetric

Partager

More