Skip to Main content Skip to Navigation
Journal articles

From constrained to Unconstrained Maximum Agreement Subtree in Linear Time

Vincent Berry 1 Zeshan S. Peng 2, * Hing-Fung Ting 2 
* Corresponding author
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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Vincent Berry Connect in order to contact the contributor
Submitted on : Tuesday, September 23, 2008 - 7:32:09 PM
Last modification on : Friday, August 5, 2022 - 3:02:17 PM
Long-term archiving on: : Friday, June 4, 2010 - 11:44:18 AM


Files produced by the author(s)


  • HAL Id : lirmm-00324070, version 1



Vincent Berry, Zeshan S. 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⟩



Record views


Files downloads