Department of Mathematics and Physics, North Carolina Central University, Durham, NC, USA,
Bull Math Biol. 2013 Oct;75(10):1879-90. doi: 10.1007/s11538-013-9874-x. Epub 2013 Aug 8.
Recently, we have shown that calculating the minimum-temporal-hybridization number for a set [Formula: see text] of rooted binary phylogenetic trees is NP-hard and have characterized this minimum number when [Formula: see text] consists of exactly two trees. In this paper, we give the first characterization of the problem for [Formula: see text] being arbitrarily large. The characterization is in terms of cherries and the existence of a particular type of sequence. Furthermore, in an online appendix to the paper, we show that this new characterization can be used to show that computing the minimum-temporal hybridization number for two trees is fixed-parameter tractable.
最近，我们已经证明计算一组[公式：见正文]有根二元系统发生树的最小时间杂交数是 NP 难的，并在[公式：见正文]恰好由两棵树组成的情况下，刻画了这个最小数。在本文中，我们首次对[公式：见正文]为任意大的情况给出了问题的特征描述。这个特征描述是基于樱桃和特定类型序列的存在。此外，在论文的在线附录中，我们证明了这种新的特征描述可以用于证明计算两棵树的最小时间杂交数是固定参数可解的。
