Determining the Consistency of Resolved Triplets and Fan Triplets
Determining the Consistency of Resolved Triplets and Fan Triplets
复制标题
DOI：
10.1089/cmb.2017.0256
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
J. Jansson;A. Lingas;Ramesh Rajaby;W. Sung
中科院分区：
文献类型：
--
作者：
J. Jansson;A. Lingas;Ramesh Rajaby;W. Sung
[公式：一致性问题将两组解析三元组[Formula：see text]和[Formula：see text]以及两组扇形三元组[Formula：see text]和[Formula：see text]作为输入，并要求一个明显的叶子标记树，该树包含[Formula：see text]中的所有元素，并且如果存在这样的树，则不包含[Formula：see text]中的元素作为嵌入子树。本文详细描述了在各种限制条件下问题的计算复杂性如何变化。我们的主要结果是一个有效的算法，密集的输入满足[公式：见文字]，其运行时间是线性的输入的大小，因此是最佳的。
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.