Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism

详细信息	查看全文 | 推荐本文 |

• 作者：Yusaku Kaneta^a ; ^{y-kaneta@ist.hokudai.ac.jp} ; Hiroki Arimura^a ; ^{arim@ist.hokudai.ac.jp} ; Rajeev Raman^b ; ^{r.raman@leicester.ac.uk}
• 关键词：Tree matching ; Bit-parallel algorithms ; Unordered trees ; XML queries ; String matching
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 期刊代码：10_15708667
• 类别：mt
• 出版时间：July, 2012
• 卷：14
• 期：Complete
• 页码：119-135
• 文件大小：449 K

摘要

In this paper, we consider the unordered pseudo-tree matching problem, which is a problem of, given two unordered labeled trees P and T, finding all occurrences of P in T via such many-to-one matchings that preserve node labels and parent-child relationship. This problem is closely related to the tree pattern matching problem for XPath queries with child axis only. If , we present an efficient algorithm that solves the problem in time using space and preprocessing on a unit-cost arithmetic RAM model with addition, where m is the number of nodes in P, n is the number of nodes in T, h is the height of T, and w is the word length, and we assume that . We also discuss a modification of our algorithm for the unordered tree homeomorphism problem, which corresponds to the tree pattern matching problem for XPath queries with descendant axis only.