Fixed-parameter Tractability of the Maximum Agreement Supertree Problem

Sylvain Guillemot 1 Vincent Berry 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a ground set $L$ of labels and a collection of trees whose leaves are bijectively labelled by some elements of $L$, the Maximum Agreement Supertree problem (\pSMAST) is the following: find a tree $T$ on a largest label set $L' \subseteq L$ that homeomorphically contains every input tree restricted to $L'$. The problem finds applications in phylogenetics, databases and data mining. In this paper we focus on the parameterized complexity of this NP-hard problem. We consider different combinations of parameters for SMAST as well as particular cases, providing both FPT algorithms and intractability results.
Type de document :
Communication dans un congrès
CPM: Combinatorial Pattern Matching, 2007, Montpellier, France. 18th Annual Combinatorial Pattern Matching Symposium, LNCS (4580), pp.274-285, 2007
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00130406
Contributeur : Sylvain Guillemot <>
Soumis le : mardi 27 février 2007 - 12:18:47
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 21 septembre 2010 - 12:54:10

Fichiers

Identifiants

  • HAL Id : lirmm-00130406, version 2

Collections

Citation

Sylvain Guillemot, Vincent Berry. Fixed-parameter Tractability of the Maximum Agreement Supertree Problem. CPM: Combinatorial Pattern Matching, 2007, Montpellier, France. 18th Annual Combinatorial Pattern Matching Symposium, LNCS (4580), pp.274-285, 2007. 〈lirmm-00130406v2〉

Partager

Métriques

Consultations de la notice

165

Téléchargements de fichiers

55