Jansson Jesper, Lingas Andrzej, Rajaby Ramesh, Sung Wing-Kin
1 Department of Computing, The Hong Kong Polytechnic University , Hung Hom, Kowloon, Hong Kong .
2 Department of Computer Science, Lund University , Lund, Sweden .
J Comput Biol. 2018 Jul;25(7):740-754. doi: 10.1089/cmb.2017.0256. Epub 2018 Feb 16.
The [Formula: see text] Consistency problem takes as input two sets [Formula: see text] and [Formula: see text] of resolved triplets and two sets [Formula: see text] and [Formula: see text] of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in [Formula: see text] and no elements in [Formula: see text] as embedded subtrees, if such a tree exists. This article presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying [Formula: see text] whose running time is linear in the size of the input and therefore optimal.
[公式：见正文]一致性问题以两个已解析三元组的集合[公式：见正文]和[公式：见正文]以及两个扇形三元组的集合[公式：见正文]和[公式：见正文]作为输入，并询问是否存在一棵具有独特叶标签的树，该树包含[公式：见正文]中的所有元素且不包含[公式：见正文]中的任何元素作为嵌入子树（如果这样的树存在）。本文详细描述了该问题在各种限制下计算复杂度是如何变化的。我们的主要结果是一种针对满足[公式：见正文]的密集输入的高效算法，其运行时间与输入大小成线性关系，因此是最优的。
