Computing all subtree repeats in ordered trees

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

doi:10.1016/j.ipl.2012.09.001

Computing all subtree repeats in ordered 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: Contribution to Journal › Article › Academic › peer-review

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.

Original language	English
Pages (from-to)	958-962
Number of pages	5
Journal	Information Processing Letters
Volume	112
Issue number	24
DOIs	https://doi.org/10.1016/j.ipl.2012.09.001
Publication status	Published - 31 Dec 2012
Externally published	Yes

Funding

E-mail address: [email protected] (M. Christou). 1 Supported by the NSF-funded iPlant Collaborative (NSF 0735191).

Keywords

Algorithms
Strings
Subtree repeats
Trees

Access to Document

10.1016/j.ipl.2012.09.001

Persistent URL (handle)

Persistent link

Cite this

@article{2a575685717f4cc0a9b4f8f9c518f577,

title = "Computing all subtree repeats in ordered trees",

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, Strings, Subtree repeats, Trees",

author = "Michalis Christou and Maxime Crochemore and Tom{\'a}{\v s} Flouri and Iliopoulos, \{Costas S.\} and Jan Janou{\v s}ek and Bo{\v r}ivoj Melichar and Pissis, \{Solon P.\}",

year = "2012",

month = dec,

day = "31",

doi = "10.1016/j.ipl.2012.09.001",

language = "English",

volume = "112",

pages = "958--962",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "24",

}

TY - JOUR

T1 - Computing all subtree repeats in ordered 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 - 2012/12/31

Y1 - 2012/12/31

N2 - 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.

AB - 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.

KW - Algorithms

KW - Strings

KW - Subtree repeats

KW - Trees

UR - https://www.scopus.com/pages/publications/84866124239

UR - https://www.scopus.com/pages/publications/84866124239#tab=citedBy

U2 - 10.1016/j.ipl.2012.09.001

DO - 10.1016/j.ipl.2012.09.001

M3 - Article

AN - SCOPUS:84866124239

SN - 0020-0190

VL - 112

SP - 958

EP - 962

JO - Information Processing Letters

JF - Information Processing Letters

IS - 24

ER -

Computing all subtree repeats in ordered trees

Abstract

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this