Kernel and fast algorithm for dense triplet inconsistency

S. Guillemot, M. Mnich

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

Abstract

We study the parameterized complexity of inferring supertrees from sets of rooted triplets, an important problem in phylogenetics. For a set L of labels and a dense set of triplets distinctly leaf-labeled by 3-subsets of L we seek a tree distinctly leaf-labeled by L and containing all but at most p triplets from R as homeomorphic subtree. Our results are the first polynomial kernel for this problem, with O(p^2) labels, and a subexponential fixed-parameter algorithm running in time 2^{p^{1/3} log p} + O(n^4).
Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation (7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings)
EditorsJ. Kratochvil, A. Li, J. Fiala, P. Kolman
Place of PublicationBerlin
PublisherSpringer
Pages247-257
ISBN (Print)978-3-642-13561-3
DOIs
Publication statusPublished - 2010
Eventconference; Theory and Applications of Models of Computation (7th Annual Conference, TAMC 2010); 2010-06-07; 2010-06-11 -
Duration: 7 Jun 201011 Jun 2010

Publication series

NameLecture Notes in Computer Science
Volume6108
ISSN (Print)0302-9743

Conference

Conferenceconference; Theory and Applications of Models of Computation (7th Annual Conference, TAMC 2010); 2010-06-07; 2010-06-11
Period7/06/1011/06/10
OtherTheory and Applications of Models of Computation (7th Annual Conference, TAMC 2010)

Fingerprint

Dive into the research topics of 'Kernel and fast algorithm for dense triplet inconsistency'. Together they form a unique fingerprint.

Cite this