On the complexity of finding a largest common subtree of bounded degree

DOI10.1016/J.TCS.2014.10.012MaRDI QIDQ2348030zbMATH OpenOpenAlexFDO

Authors Tatsuya Akutsu, Takeyuki Tamura, Avraham A. Melkman, Atsuhiro Takasu

Publication date 10 June 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.10.012

zbMATH Keywords

dynamic programmingparameterized complexitytree edit distanceunordered trees

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)

Recommendations

• On the complexity of finding a largest common subtree of bounded degree
• Improved approximation of the largest common subtree of two unordered trees of bounded height
• Faster algorithms for the maximum common subtree isomorphism problem
• Algorithms and Computation
• FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES

Cites work

• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• An optimal decomposition algorithm for tree edit distance
• Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees
• Efficient exponential time algorithms for edit distance between unordered trees
• Exact algorithms for computing the tree edit distance between unordered trees
• Exact and approximate algorithms for unordered tree matching
• scientific article; zbMATH DE number 1820633 (Why is no real title available?)
• Improved MAX SNP-hard results for finding an edit distance between unordered trees
• On the complexity of finding a largest common subtree of bounded degree
• On the editing distance between unordered labeled trees
• Ordered and Unordered Tree Inclusion
• Parametrized complexity theory.
• Some MAX SNP-hard results concerning unordered labeled trees
• The \(k\)-cardinality assignment problem
• The Tree-to-Tree Correction Problem

Cited in

(11)

• On the approximation of largest common subtrees and largest common point sets
• On the computational complexity of the rooted subtree prune and regraft distance
• Enumeration of subtrees and BC-subtrees with maximum degree no more than \(k\) in trees
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• On the complexity of finding a largest common subtree of bounded degree
• Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay
• On the Complexity of Extracting Subtree with Keeping Distinguishability
• About the largest subtree common to several X-trees
• Finding largest common embeddable subtrees
• Faster algorithms for the maximum common subtree isomorphism problem
• Improved approximation of the largest common subtree of two unordered trees of bounded height

Describes a project that uses

Uses Software

• KEGG

This page was built for publication: On the complexity of finding a largest common subtree of bounded degree

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