| Abstract |
|
The tree pattern matching problem over labeled trees is
addressed in this paper. Several tree pattern matching algorithms
are known which are based on the decomposition
of the pattern into strings, with each string representing
a root-to-leaf path. Among these, Alfs T. Berztiss gave
a simple tree pattern matching algorithm which remained
unknown to the research community. In this paper, the tree
pattern matching algorithm of Berztiss is reviewed, its correctness
is established, and its complexity is shown to be
O(mn) time and space in the worst case and O(n) on the
average, where n is the text size and m is the pattern size.
|
 Additional Information
|
Index Terms- design and analysis of algorithms, combinatorial problems, tree pattern matching, subtree isomorphism
Citation:
Gabriel Valiente,
"On the Algorithm of Berztiss for Tree Pattern Matching,"
enc,
pp. 43-49,
Fifth Mexican International Conference in Computer Science (ENC'04),
2004
|
