Fixed-parameter Tractability of the Maximum Agreement Supertree Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2007

Fixed-parameter Tractability of the Maximum Agreement Supertree Problem

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.
Fichier principal
Vignette du fichier
RR07005.pdf (237.35 Ko) Télécharger le fichier

Dates and versions

lirmm-00130406 , version 1 (27-02-2007)
lirmm-00130406 , version 2 (27-02-2007)

Identifiers

  • HAL Id : lirmm-00130406 , version 2

Cite

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⟩
180 View
206 Download

Share

More