限制性樹包含偵測演算法

A Top Down Algorithm for Constrained Tree Inclusion Problem

蕭宇翔(Yu-Hsiang Hsiao)

指導教授 ： 張克寧

國立暨南國際大學/科技學院/資訊工程學系/博士(2015年)

https://doi.org/10.6837/NCNU.2015.00082

摘要

“限制性樹包含問題”是一種類似“樹包含問題”的研究題目，由Gabriel Valiente 率先提出。假設存在兩棵樹P和T，P包含在T裡面若且唯若P 與T’同構，而T’為T 經過一系列的節點刪除所形成，而樹包含問題就是決定P 是否可以包含在T裡面。在這裡所討論的樹是圖論裡的有序樹。而限制性樹包含問題不同於樹包含問題的地方，在於被刪除的節點限制在分枝度小於或等於二的情況。 由於樹包含問題無法找出在結構上相似的樹，所以設計出限制性樹包含問題。Gabriel Valiente首先提出由後序搜尋的演算法解限制性樹包含問題。其演算法可以應用在有序樹或者一般樹中。在有序樹的情況下，其時間複雜度為O(mn)，空間複雜度為O(mn) ，其中m 為P 的節點數，n 為T的節點數。 本論文使用的策略為前序搜尋。這一種方式比較容易實作，也比較直覺。其時間複雜度為O(mn)，空間複雜度為O(m+n)。在空間的使用上除了P和T所佔的空間，演算法的運算本身只耗費O(m)，大幅降低解這個問題所需的儲存空間。

關鍵字

限制性樹包含問題 ； 樹包含問題 ； 有序樹

並列摘要

An ordered labeled tree is a tree which nodes are labeled and in which the left-to-right order among siblings is significant. Given two ordered labeled trees P and T, the tree inclusion problem is to determine if it is possible to obtain the pattern tree P from target tree T through a sequence of deleting some nodes of T. If this is the case, we say P is included in T. When the deletion is limited to nodes with degree one or two, the restricted problem is called constrained tree inclusion problem.
The constrained tree inclusion problem is more sensitive to the structure of the pattern tree than the general tree inclusion problem. Valiente first proposed a bottom up algorithm which solves the problem in quadratic time and space. We present a top down matching algorithm which solves constrained tree inclusion problem in square time but uses only linear space. The benefit of the top down algorithm is its simplicity. It is easy to implement the algorithm and no extra complex data structures are used.

並列關鍵字

Constrained tree inclusion ； Tree inclusion ； Ordered tree

參考文獻

[1] P. Bille and I.L. Gortz. The tree inclusion problem: In linear space and faster. ACM Transactions on Algorithms (TALG), 7(3):38, 2011.

[2] K.N. Chang, Y.H. Hsiao, and C.C. Liao. A top down algorithm for constrained tree inclusion. Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, 2011.

[3] Y. Chen and Y. Chen. A new tree inclusion algorithm. Information Processing Letters, 98(6):253–262, 2006.

[4] Y. Chen and Y. Chen. On the tree inclusion problem. In International Conference on Computer, Networks and Communication Engineer- ing (ICCNCE 2013). Atlantis Press, 2013.

[5] H.L. Cheng and B.F. Wang. On Chen and Chen’s new tree inclusion algorithm. Information Processing Letters, 103(1):14–18, 2007.