文章基本信息

标题：Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees
本地全文：下载
作者：Viet Tung Hoang ; Wing-Kin Sung
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：1
页码：361-372
DOI：10.4230/LIPIcs.STACS.2008.1357
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Consider a set of labels $L$ and a set of trees ${mathcal T} = { {mathcal T}^{(1), {mathcal T}^{(2), ldots, {mathcal T}^{(k) $ where each tree ${mathcal T}^{(i)$ is distinctly leaf-labeled by some subset of $L$. One fundamental problem is to find the biggest tree (denoted as supertree) to represent $mathcal T}$ which minimizes the disagreements with the trees in ${mathcal T}$ under certain criteria. This problem finds applications in phylogenetics, database, and data mining. In this paper, we focus on two particular supertree problems, namely, the maximum agreement supertree problem (MASP) and the maximum compatible supertree problem (MCSP). These two problems are known to be NP-hard for $k geq 3$. This paper gives the first polynomial time algorithms for both MASP and MCSP when both $k$ and the maximum degree $D$ of the trees are constant.
关键词：Maximum agreement supertree; maximum compatible supertree