TY - JOUR
T1 - Kernel and fast algorithm for dense triplet inconsistency
AU - Guillemot, S.
AU - Mnich, M.
PY - 2013
Y1 - 2013
N2 - 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 T 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 k triplets from T as homeomorphic subtree. Our results are the first polynomial kernel for this problem, with O(k^2) labels, and a subexponential fixed-parameter algorithm running in time O(|L|^4)+2^{O(k^{1/3}logk)}.
AB - 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 T 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 k triplets from T as homeomorphic subtree. Our results are the first polynomial kernel for this problem, with O(k^2) labels, and a subexponential fixed-parameter algorithm running in time O(|L|^4)+2^{O(k^{1/3}logk)}.
U2 - 10.1016/j.tcs.2012.12.032
DO - 10.1016/j.tcs.2012.12.032
M3 - Article
SN - 0304-3975
VL - 494
SP - 134
EP - 143
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -