Computing all subtree repeats in ordered trees

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.
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00836959
Contributor : Maxime Crochemore <>
Submitted on : Friday, June 21, 2013 - 6:26:54 PM
Last modification on : Thursday, April 19, 2018 - 2:24:03 PM

Identifiers

Citation

Michalis Christou, Maxime Crochemore, Tomas Flouri, Costas Iliopoulos, Jan Janousek, et al.. Computing all subtree repeats in ordered trees. Information Processing Letters, Elsevier, 2012, 112 (24), pp.958-962. ⟨10.1016/j.ipl.2012.09.001⟩. ⟨hal-00836959⟩

Share

Metrics

Record views

221