Efficient exponential-time algorithms for edit distance between unordered trees
From MaRDI portal
Publication:2442818
DOI10.1016/j.jda.2013.09.001zbMath1284.05259MaRDI QIDQ2442818
Atsuhiro Takasu, Takeyuki Tamura, Daiji Fukagawa, Tatsuya Akutsu
Publication date: 1 April 2014
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2013.09.001
05C05: Trees
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Cites Work
- A survey on tree edit distance and related problems
- Exact algorithms for computing the tree edit distance between unordered trees
- A simplified NP-complete satisfiability problem
- Improved approximation of the largest common subtree of two unordered trees of bounded height
- On the editing distance between unordered labeled trees
- Some MAX SNP-hard results concerning unordered labeled trees
- Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees
- An optimal decomposition algorithm for tree edit distance
- Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees
- On Tree-Constrained Matchings and Generalizations
- The Tree-to-Tree Correction Problem
- A Visual Explanation of Jensen's Inequality
- Ordered and Unordered Tree Inclusion
- Exact and approximate algorithms for unordered tree matching