Computing all subtree repeats in ordered trees

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

doi:10.1016/j.ipl.2012.09.001

Journal articles

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 : Wednesday, February 26, 2020 - 7:06:06 PM

Computing all subtree repeats in ordered trees

Identifiers

Collections

Citation

Export

Metrics

308

Contact

Informations

Computing all subtree repeats in ordered trees

Identifiers

Collections

Citation

Export

Share

Metrics

308

Contact

Informations