From constrained to Unconstrained Maximum Agreement Subtree in Linear Time - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Algorithmica Year : 2008

From constrained to Unconstrained Maximum Agreement Subtree in Linear Time

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.
Fichier principal
Vignette du fichier
kmcast.pdf (199.36 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
138 View
376 Download

Altmetric

Share

More