On Regular Tree Embeddings
Weimin Chen, Volker Turau · SIAM Journal on Computing · 1999
Regular trees are a natural extension of finite trees, which have many applications. The path-embedding problem is to determine whether a regular tree S can be obtained from another regular tree T by deleting (probably infinitely many) subtrees of T. This paper explores efficient algorithms for the path-embedding problem in ordered and unordered trees. Given two regular trees S and T represented by rational graphs, our algorithms solve the ordered version of path-embedding problem in O(|E_S||E_T|) time and the unordered version in O(|E S ||E T |D S D T ) time. Here |E S | denotes the number of edges in the rational graph for S, and D S denotes the maximum outdegree of a vertex inS. We also demonstrate that our approach can be applied to pattern matching problems for regular trees recently studied by Fu J. Algorithms, 22 (1997), pp. 372--391].