@inproceedings{61659ec1957a4d9caa0b540e4758dd1d,

title = "Kernel and fast algorithm for dense triplet inconsistency",

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).",

author = "S. Guillemot and M. Mnich",

year = "2010",

doi = "10.1007/978-3-642-13562-0_23",

language = "English",

isbn = "978-3-642-13561-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "247--257",

editor = "J. Kratochvil and A. Li and J. Fiala and P. Kolman",

booktitle = "Theory and Applications of Models of Computation (7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings)",

address = "Germany",

note = "conference; Theory and Applications of Models of Computation (7th Annual Conference, TAMC 2010); 2010-06-07; 2010-06-11 ; Conference date: 07-06-2010 Through 11-06-2010",

}