On the Complexity of Finding a Largest Common Subtree of Bounded Degree
On the Complexity of Finding a Largest Common Subtree of Bounded Degree
复制标题
关于寻找有界度最大公共子树的复杂性
DOI：
10.1007/978-3-642-40164-0_4
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Atsuhiro Takasu
中科院分区：
文献类型：
--
作者：
Tatsuya Akutsu;Takeyuki Tamura;Avraham A. Melkman;Atsuhiro Takasu
最大的常见子树问题是找到两个具有最大基数或权重的输入有根树的节点子集之间的双射映射，以保留标签和祖先关系。已知该问题对于无序树来说是 NP 困难的。在本文中，我们考虑一种受限无序情况，其中公共子树的最大出度受常数 D 限制。我们提出了一种 O (n D) 时间算法，其中 n 是两个输入树的最大大小，这改进了之前的 O (n 2 D) 时间算法。我们还提出了 O ((H 2⋅ 2 2 H− 1⋅ D 2 H) D− 1 poly (n)) 时间算法，其中 H 是两个输入树的最大高度。
The largest common subtree problem is to find a bijective mapping between subsets of nodes of two input rooted trees of maximum cardinality or weight that preserves labels and ancestry relationship. The problem is known to be NP-hard for unordered trees. In this paper, we consider a restricted unordered case in which the maximum outdegree of a common subtree is bounded by a constant D. We present an O (n D) time algorithm where n is the maximum size of two input trees, which improves a previous O (n 2 D) time algorithm. We also present an O ((H 2⋅ 2 2 H− 1⋅ D 2 H) D− 1 poly (n)) time algorithm, where H is the maximum height of two input trees.