Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees
DOI10.1016/J.TCS.2012.11.017zbMATH Open1258.68102OpenAlexW2146138435MaRDI QIDQ1935809FDOQ1935809
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
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
dynamic programmingapproximation algorithmsparameterized algorithmstree edit distanceunordered trees
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)
Cited In (16)
- On the computational complexity of the rooted subtree prune and regraft distance
- Trees with large numbers of subtrees
- Title not available (Why is that?)
- Improved approximation of the largest common subtree of two unordered trees of bounded height
- On the complexity of finding a largest common subtree of bounded degree
- Approximate labelled subtree homeomorphism
- On the complexity of finding a largest common subtree of bounded degree
- New and improved algorithms for unordered tree inclusion
- Some MAX SNP-hard results concerning unordered labeled trees
- On the parameterized complexity of the multi-MCT and multi-MCST problems
- Identifying approximately common substructures in trees based on a restricted edit distance
- Approximation and special cases of common subtrees and editing distance
- Efficient exponential-time algorithms for edit distance between unordered trees
- Tai mapping hierarchy for rooted labeled trees through common subforest
- Tractable and intractable variations of unordered tree edit distance
- Combinatorial Pattern Matching
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)
