Computing all subtree repeats in ordered trees

Michalis Christou; Maxime Crochemore; Tomas Flouri; Costas Iliopoulos; Jan Janousek; Borivoj Melichar; Solon Pissis

Computing all subtree repeats in ordered trees

Michalis Christou ¹ Maxime Crochemore ^{1, 2} Tomas Flouri ³ Costas Iliopoulos ¹ Jan Janousek ³ Borivoj Melichar ³ 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

Domain :

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

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

Computing all subtree repeats in ordered trees

Identifiers

Collections

Citation

Export

Metrics

229

Contact

Computing all subtree repeats in ordered trees

Identifiers

Collections

Citation

Export

Share

Metrics

229

Contact