Skip to Main content Skip to Navigation
Journal articles

From constrained to Unconstrained Maximum Agreement Subtree in Linear Time

Vincent Berry 1 Zeshan 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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324070
Contributor : Vincent Berry <>
Submitted on : Tuesday, September 23, 2008 - 7:32:09 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on: : Friday, June 4, 2010 - 11:44:18 AM

Files

kmcast.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

282

Files downloads

407