An optimal algorithm for computing all subtree repeats in trees

DOI10.1098/RSTA.2013.0140MaRDI QIDQ2955638zbMATH OpenOpenAlexWikidataFDO

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

Publication date 13 January 2017

Published in Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1098/rsta.2013.0140

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• An optimal algorithm for computing all subtree repeats in trees
• Computing all subtree repeats in ordered trees
• Approximate labelled subtree homeomorphism
• Combinatorial Pattern Matching
• On finding common subtrees

Cites work

• Algorithms for pattern matching and discovery in RNA secondary structure
• Computing all subtree repeats in ordered trees
• Evolutionary Bioinformatics
• Finding a maximum likelihood tree is hard
• Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species
• Programming with Equations
• Tree automata for code selection

Cited in

(10)

• Trees with the mos subtrees - an algorithmic approach
• Computing all subtree repeats in ordered trees
• Efficient counting of square substrings in a tree
• An optimal algorithm for computing all subtree repeats in trees
• An Analysis of a Good Algorithm for the Subtree Problem, Corrected
• A Sub-quadratic Time and Space Complexity Solution for the Dated Tree Reconciliation Problem for Select Tree Topologies
• Subsumption algorithms based on search trees
• Find subtrees of specified weight and cycles of specified length in linear time
• A linear time and space algorithm for finding isomorphic subtrees of a binary tree
• Revisiting dynamic programming for finding optimal subtrees in trees

This page was built for publication: An optimal algorithm for computing all subtree repeats in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955638)