The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
On Regular Tree Embeddings
Weimin Chen, Volker Turau,
Pages. 288-301
Abstract 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_SD_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 in $S$. We also
demonstrate that our approach can be applied to pattern matching
problems for regular trees recently studied by Fu [{it J.
Algorithms}, 22 (1997), pp. 372-391].
Contents 1. Introduction 2. Basic definitions and rational graphs 3. Ordered embedding 3.1. Transformation 3.2. Algorithms 4. Unordered embedding 5. Comparisons with related work 6. Conclusion
Key words regular trees, directed graph pattern matching, embedding, boolean equations
Mathmatical Subject Classification 68Q25, 68Q20, 68R10