| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427665 | Information Processing Letters | 2012 | 5 Pages |
Abstract
We consider the problem of computing all subtree repeats in a given labeled ordered tree. We first transform the tree to a string representing its postfix notation, and then present an algorithm based on the bottom-up technique to solve it. The proposed algorithm consists of two phases: the preprocessing phase and the phase where all subtree repeats are computed. The linear time and space complexity of the proposed algorithm are important parts of its quality.
► Problem: computing all subtree repeats in a given unlabeled or labeled ordered tree. ► String representation of tree and bottom-up technique. ► Linear time and space complexity.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michalis Christou, Maxime Crochemore, Tomáš Flouri, Costas S. Iliopoulos, Jan Janoušek, Bořivoj Melichar, Solon P. Pissis,