An optimal algorithm for computing all subtree repeats in trees

Tomáš Flouri, Kassian Kobert, Solon P. Pissis, Alexandros Stamatakis

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

Abstract

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.

Original languageEnglish
Title of host publicationCombinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers
Pages269-282
Number of pages14
DOIs
Publication statusPublished - 1 Dec 2013
Externally publishedYes
Event24th International Workshop on Combinatorial Algorithms, IWOCA 2013 - Rouen, France
Duration: 10 Jul 201312 Jul 2013

Publication series

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

Conference

Conference24th International Workshop on Combinatorial Algorithms, IWOCA 2013
CountryFrance
CityRouen
Period10/07/1312/07/13

Fingerprint Dive into the research topics of 'An optimal algorithm for computing all subtree repeats in trees'. Together they form a unique fingerprint.

Cite this