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 -