有序樹之限制性嵌入問題研究

“限制性樹嵌入問題”是一種類似”樹嵌入問題”的研究題目，由Gabriel Valiente率先提出。假設存在兩棵樹P和T，P可以嵌入T，若且唯若P與T’ 同構，而T’ 為T經過一系列的節點刪除所形成，而樹嵌入問題就是決定P是否可以嵌入T 。在這裡的樹可以是圖論裡的有序樹或者是一般樹。而限制性樹嵌入問題不同於樹嵌入問題的地方，在於被刪除的節點限制在分枝度小於或等於二的情況下。 Gabriel Valiente論文中的演算法可以應用在有序樹或者一般樹中，其使用的策略為由後序搜尋。在有序樹的情況下，其時間複雜度為O(mn)，空間複雜度為O(mn) ，其中m為T的節點數，n為P的節點數。本論文中僅討論有序樹的情況，其使用的策略為前序搜尋。這一種方式比較容易應用，也比較直覺。其時間複雜度為O(mn*leaves(T))，空間複雜度為O(m*leaves(T)) 。雖然本論文中所提出的演算法時間複雜度比Gabriel Valiente差，可是使用的空間卻比較少，在實際的使用上，因為可以避免掉很多不必要的計算，所以在時間複雜度上會比O(mn*leaves(T))好。

關鍵字

限制性嵌入問題

並列摘要

Tree P is included in tree T, denoted as P ⊆ T, if and only P is isomorphic to T' where T' is derived from T through a sequence of node deletions. Tree inclusion problem is to determine if P ⊆ T or not. Constrained tree inclusion problem is a kind of tree inclusion problem with node deleted having degree one or two. It can be solved in polynomial time for both unordered and ordered trees. This problem first appeared in Gabriel Valiente's paper. His paper gives an algorithm in bottom-up strategy to solve the problem. The algorithm can be used in both ordered and unordered trees. The algorithm for ordered trees takes O(mn) time and additional O(mn) space. In this paper, only ordered trees are discussed. We provide a new algorithm in top-down strategy which is more intuitive. We recursively search that whether there exists an embedding from P to T. It takes O(mn*leaves(T)) time but only additional O(n*leaves(T)) space.

並列關鍵字

Constrained Tree Inclusion

參考文獻

[1] K. C. Tai, "The tree-to-tree correction problem," Journal of the ACM, vol. 26, no. 3, pp. 422-433, 1979.

Google Scholar

[2] P. Bille and I. G 'rtz, "The tree inclusion problem: In optimal space and faster," in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming. Springer, 2005.