From constrained to Unconstrained Maximum Agreement Subtree in Linear Time - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
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⟩
134 View
366 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More