Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00130406
Contributor : Sylvain Guillemot <>
Submitted on : Tuesday, February 27, 2007 - 12:18:47 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on: : Tuesday, September 21, 2010 - 12:54:10 PM

Identifiers

  • 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. pp.274-285. ⟨lirmm-00130406v2⟩

Share

Metrics

Record views

223

Files downloads

96