Efficient Algorithms for the Tree Homeomorphism Problem
Efficient Algorithms for the Tree Homeomorphism Problem
复制标题
树同态问题的高效算法
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
W. Martens
中科院分区：
文献类型：
--
作者：
M. Götz;Christoph E. Koch;W. Martens
树模式匹配是一个基本问题，在Web数据管理、XML处理和选择性数据分发中有着广泛的应用。本文针对树同胚问题，即树模式与排他传递(子孙)边的匹配问题，提出了有效的算法。我们首先证明了判定是否存在树同胚是LOGSPACE完全的，改进了目前的LOGCFL上界。作为我们的主要结果，我们给出了一个实用的算法来解决树同胚判定问题，该算法既节省空间又节省时间。该算法是LOGDCFL算法，空间消耗是强有界的，而运行时间与数据树的大小是线性的。该算法直接推广到树模式与数据树的所有子树的匹配问题，同时保持了上述的效率性质。
Tree pattern matching is a fundamental problem that has a wide range of applications in Web data management, XML processing, and selective data dissemination. In this paper we develop efficient algorithms for the tree homeomorphism problem, i.e., the problem of matching a tree pattern with exclusively transitive (descendant) edges. We first prove that deciding whether there is a tree homeomorphism is LOGSPACE-complete, improving on the current LOGCFL upper bound. As our main result we develop a practical algorithm for the tree homeomorphism decision problem that is both space- and time efficient. The algorithm is in LOGDCFL and space consumption is strongly bounded, while the running time is linear in the size of the data tree. This algorithm immediately generalizes to the problem of matching the tree pattern against all subtrees of the data tree, preserving the mentioned efficiency properties.