Skip to Main content Skip to Navigation
Journal articles

Computing all subtree repeats in ordered trees

Michalis Christou 1 Maxime Crochemore 1, 2 Tomas Flouri 3 Costas Iliopoulos 1 Jan Janousek 3 Borivoj Melichar 3 Solon Pissis 1, 4
1 Informatics
2 ligm - Laboratoire d'Informatique Gaspard-Monge
3 TCS-CTU - Department of Theoretical Computer Science
4 DCS - Department of Computer Science
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.
Keywords : Algorithms Trees Strings Subtree repeats
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 : Wednesday, February 26, 2020 - 7:06:06 PM

Identifiers

Collections

ENPC | LIGM | PARISTECH | LIGM_ALGO | UNIV-MLV | UPEC-UPEM | CNRS | LIGM_MOA

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

359