Efficient exponential-time algorithms for edit distance between unordered trees

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

zbMATH Keywords

algorithm; bipartite matching; edit distance; unordered tree

Mathematics Subject Classification ID

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

Unnamed Item, New and improved algorithms for unordered tree inclusion

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