Computing all subtree repeats in ordered ranked trees

Michalis Christou*, Maxime Crochemore, Tomáš Flouri, Costas S. Iliopoulos, Jan Janoušek, Bořivoj Melichar, Solon P. Pissis

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We consider the problem of finding all subtree repeats in a given ordered ranked tree. Specifically, we transform the given tree to a string representing its postfix notation, and then propose an algorithm based on the bottom-up technique. The proposed algorithm is divided into two phases: the preprocessing phase, and the phase where all subtree repeats are computed. The linear runtime of the algorithm, as well as the use of linear auxiliary space, are important aspects of its quality.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 18th International Symposium, SPIRE 2011, Proceedings
Pages338-343
Number of pages6
DOIs
Publication statusPublished - 17 Oct 2011
Externally publishedYes
Event18th International Symposium on String Processing and Information Retrieval, SPIRE 2011 - Pisa, Italy
Duration: 17 Oct 201121 Oct 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7024 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Symposium on String Processing and Information Retrieval, SPIRE 2011
Country/TerritoryItaly
CityPisa
Period17/10/1121/10/11

Fingerprint

Dive into the research topics of 'Computing all subtree repeats in ordered ranked trees'. Together they form a unique fingerprint.

Cite this