Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees

DOI10.1016/J.TCS.2012.11.017MaRDI QIDQ1935809zbMATH OpenOpenAlexFDO

Authors Tatsuya Akutsu, Daiji Fukagawa, Magnús M. Halldórsson, Atsuhiro Takasu, Keisuke Tanaka

Publication date 19 February 2013

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

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

zbMATH Keywords

dynamic programmingapproximation algorithmsparameterized algorithmstree edit distanceunordered trees

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

Recommendations

• Approximation and special cases of common subtrees and editing distance
• Exact algorithms for computing the tree edit distance between unordered trees
• Improved approximation of the largest common subtree of two unordered trees of bounded height
• A constrained edit distance between unordered labeled trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems

Cited in

(16)

• On the complexity of finding a largest common subtree of bounded degree
• On the parameterized complexity of the multi-MCT and multi-MCST problems
• Tai mapping hierarchy for rooted labeled trees through common subforest
• scientific article; zbMATH DE number 7561381 (Why is no real title available?)
• Approximation and special cases of common subtrees and editing distance
• On the complexity of finding a largest common subtree of bounded degree
• Approximate labelled subtree homeomorphism
• Efficient exponential-time algorithms for edit distance between unordered trees
• Improved approximation of the largest common subtree of two unordered trees of bounded height
• Some MAX SNP-hard results concerning unordered labeled trees
• Identifying approximately common substructures in trees based on a restricted edit distance
• Tractable and intractable variations of unordered tree edit distance
• On the computational complexity of the rooted subtree prune and regraft distance
• Trees with large numbers of subtrees
• Combinatorial Pattern Matching
• New and improved algorithms for unordered tree inclusion

This page was built for publication: Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees

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