TY - GEN

T1 - An optimal algorithm for computing all subtree repeats in trees

AU - Flouri, Tomáš

AU - Kobert, Kassian

AU - Pissis, Solon P.

AU - Stamatakis, Alexandros

PY - 2013/12/1

Y1 - 2013/12/1

N2 - Given a labeled tree T, our goal is to group repeating subtrees of T into equivalence classes with respect to their topologies and the node labels. We present an explicit, simple, and time-optimal algorithm for solving this problem for unrooted unordered labeled trees, and show that the running time of our method is linear with respect to the size of T. By unordered, we mean that the order of the adjacent nodes (children/neighbors) of any node of T is irrelevant. An unrooted tree T does not have a node that is designated as root and can also be referred to as an undirected tree. We show how the presented algorithm can easily be modified to operate on trees that do not satisfy some or any of the aforementioned assumptions on the tree structure; for instance, how it can be applied to rooted, ordered or unlabeled trees.

AB - Given a labeled tree T, our goal is to group repeating subtrees of T into equivalence classes with respect to their topologies and the node labels. We present an explicit, simple, and time-optimal algorithm for solving this problem for unrooted unordered labeled trees, and show that the running time of our method is linear with respect to the size of T. By unordered, we mean that the order of the adjacent nodes (children/neighbors) of any node of T is irrelevant. An unrooted tree T does not have a node that is designated as root and can also be referred to as an undirected tree. We show how the presented algorithm can easily be modified to operate on trees that do not satisfy some or any of the aforementioned assumptions on the tree structure; for instance, how it can be applied to rooted, ordered or unlabeled trees.

UR - http://www.scopus.com/inward/record.url?scp=84893031135&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893031135&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-45278-9_23

DO - 10.1007/978-3-642-45278-9_23

M3 - Conference contribution

AN - SCOPUS:84893031135

SN - 9783642452772

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 269

EP - 282

BT - Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers

T2 - 24th International Workshop on Combinatorial Algorithms, IWOCA 2013

Y2 - 10 July 2013 through 12 July 2013

ER -