The tree inclusion problem is, given two node-labeled trees $P$ and $T$ (the ``pattern tree'' and the ``target tree''), to locate every minimal subtree in $T$ (if any) that can be obtained by applying a sequence of node insertion operations to $P$. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is a classic algorithm by Kilpel\"{a}inen and Mannila from 1995 that runs in $O(2^{2d} mn)$ time, where $m$ and $n$ are the sizes of the pattern and target trees, respectively, and $d$ is the degree of the pattern tree. Here, we develop a new algorithm that runs in $O(2^{d} mn^2)$ time, improving the exponential factor from $2^{2d}$ to $2^d$ by considering a particular type of ancestor-descendant relationships that is suitable for dynamic programming. We also study restricted variants of the unordered tree inclusion problem.
翻译：树的融入问题是,考虑到两个标有节点的树(P$和$T$)(“树”和“目标树”),树的融入问题在于将每个最低的亚树以美元(如果有的话)定位为$(如果有的话),这是通过对$P美元应用一个节点插入操作序列可以获得的。虽然订购的树融入问题在多元时间中是可以溶解的,但未排序的树融入问题是硬的。后者目前最快的算法是1995年Kilpel\"{a}inen和Mannila的经典算法,用$(2 ⁇ 2d}m)计算,用美元计算,其中美元和美元分别是图案和目标树木的大小,美元是图案树的程度。在这里,我们开发了一个新的以$(2 ⁇ d} mn ⁇ 2美元运行的新算法,将指数系数从2 ⁇ 2d}提高到2 ⁇ d$,通过考虑适合动态编程的特定类型的祖先-后代关系类型,我们还研究了未排序的树问题有限制的变式。
相关内容
微信扫码咨询专知VIP会员