On the Approximation of Computing Evolutionary Trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2005

On the Approximation of Computing Evolutionary Trees


Given a set of leaf-labelled trees with identical leaf sets, the well-known MAST problem consists of finding a subtree homeomorphi- cally included in all input trees and with the largest number of leaves. MAST and its variant called MCT are of particular interest in computa- tional biology. This paper presents positive and negative results on the approximation of MAST, MCT and their complement versions, denoted CMAST and CMCT. For CMAST and CMCT on rooted trees we give 3-approximation algo- rithms achieving significantly lower running times than those previously known. In particular, the algorithm for CMAST runs in linear time. The approximation threshold for CMAST, resp. CMCT, is shown to be the same whenever collections of rooted trees or of unrooted trees are considered. Moreover, hardness of approximation results are stated for CMAST, CMCT and MCT on small number of trees, and for MCT on unbounded number of trees.


Other [cs.OH]
Fichier principal
Vignette du fichier
D524.PDF (228.65 Ko) Télécharger le fichier

Dates and versions

lirmm-00106451 , version 1 (16-10-2006)



Vincent Berry, Sylvain Guillemot, Nicolas François, Christophe Paul. On the Approximation of Computing Evolutionary Trees. COCOON: Computing and Combinatorics Conference, Aug 2005, Kunming, China. pp.115-125, ⟨10.1007/11533719_14⟩. ⟨lirmm-00106451⟩
105 View
361 Download



Gmail Facebook X LinkedIn More