Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem
Extended Abstract
verfasst von : Sylvain Guillemot, Vincent Berry
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 (SMAST) is the following: find a tree
T
on a largest label set
L
′ ⊆
L
that homeomorphically contains every input tree restricted to
L
′. The problem finds applications in several fields, e.g. phylogenetics. 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.