Rooted Maximum Agreement Supertrees
Rooted Maximum Agreement Supertrees
复制标题
DOI：
10.1007/s00453-004-1147-5
复制
发表时间：
2004-04
期刊：
影响因子：
1.1
通讯作者：
J. Jansson;Joseph H.-K. Ng;K. Sadakane;W. Sung
中科院分区：
文献类型：
--
作者：
J. Jansson;Joseph H.-K. Ng;K. Sadakane;W. Sung
给定一个有根的无序树集合T，其中每个T_i \in \T$被一个集合明确地标记为叶，并且集合可以重叠，最大一致超树问题（MASP）是构造一个具有叶集合\cup$_{T_i \in \T} \Lambda（T_i）$的明确地标记为叶的树，使得对于每个T_i \in \T$，的拓扑限制同构于的拓扑限制。$n = \left| $\cup$_{T_i \in \T} \Lambda（T_i）\right| $，$k =|\T| $D = \max_{T_i \in \T}\{\deg（T_i）\}$。我们首先证明了MASP在时间上是可以求解的，时间和时间是不受限制的。在此基础上，我们提出了一个求解MASP的算法，其运行时间是多项式的，如果。另一方面，我们证明了MASP是NP-困难的任何fixedwhenis无限制的，也NP-困难的任何fixedwhenis无限制的，即使每个输入树需要包含最多三个叶子。最后，我们描述了一个多项式时间近似算法的MASP。
Given a set $\T$ of rooted, unordered trees, where each $T_i \in \T$ is distinctly leaf-labeled by a setand where the setsmay overlap, the maximum agreement supertree problem~(MASP) is to construct a distinctly leaf-labeled treewith leaf set\cup$_{T_i \in \T} \Lambda(T_i)$ such thatis maximized and for each $T_i \in \T$, the topological restriction oftois isomorphic to the topological restriction ofto. Let $n = \left| $\cup$_{T_i \in \T} \Lambda(T_i)\right|$, $k = |\T|$, and $D = \max_{T_i \in \T}\{\deg(T_i)\}$. We first show that MASP withcan be solved intime, which iswhenandwhenis unrestricted. We then present an algorithm for MASP withwhose running time is polynomial if. On the other hand, we prove that MASP is NP-hard for any fixedwhenis unrestricted, and also NP-hard for any fixedwhenis unrestricted even if each input tree is required to contain at most three leaves. Finally, we describe a polynomial-time-approximation algorithm for MASP.