TY - GEN
T1 - Computing all subtree repeats in ordered ranked trees
AU - Christou, Michalis
AU - Crochemore, Maxime
AU - Flouri, Tomáš
AU - Iliopoulos, Costas S.
AU - Janoušek, Jan
AU - Melichar, Bořivoj
AU - Pissis, Solon P.
PY - 2011/10/17
Y1 - 2011/10/17
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=80053985964&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80053985964&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-24583-1_33
DO - 10.1007/978-3-642-24583-1_33
M3 - Conference contribution
AN - SCOPUS:80053985964
SN - 9783642245824
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 338
EP - 343
BT - String Processing and Information Retrieval - 18th International Symposium, SPIRE 2011, Proceedings
T2 - 18th International Symposium on String Processing and Information Retrieval, SPIRE 2011
Y2 - 17 October 2011 through 21 October 2011
ER -