Kernel and fast algorithm for dense triplet inconsistency

详细信息    查看全文

• 作者：Sylvain Guillemot^a ; ^{sylvain.guillemot@uni-jena.de} ; Matthias Mnich^b ; ^{m.mnich@tue.nl}
• 刊名：Theoretical Computer Science
• 出版年：2013
• 出版时间：8 July, 2013
• 年：2013
• 卷：494
• 期：Complete
• 页码：134-143
• 全文大小：267 K

文摘

We study the parameterized complexity of inferring supertrees from sets of rooted triplets, an important problem in phylogenetics. For a set of labels and a dense set of triplets distinctly leaf-labeled by 3-subsets of , we seek a tree distinctly leaf-labeled by and containing all but at most triplets from? as homeomorphic subtree. Our results are the first polynomial kernel for this problem, with labels, and a subexponential fixed-parameter algorithm running in time .