Efficient exponential-time algorithms for edit distance between unordered trees

DOI10.1016/j.jda.2013.09.001zbMath1284.05259OpenAlexW2069551218MaRDI 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

algorithmbipartite matchingedit distanceunordered tree

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Unnamed Item ⋮ New and improved algorithms for unordered tree inclusion

Cites Work

• Unnamed Item
• 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
• 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

This page was built for publication: Efficient exponential-time algorithms for edit distance between unordered trees