Efficient exponential-time algorithms for edit distance between unordered trees

DOI10.1016/J.JDA.2013.09.001MaRDI QIDQ2442818zbMATH OpenOpenAlexFDO

Authors Tatsuya Akutsu, Takeyuki Tamura, Daiji Fukagawa, Atsuhiro Takasu

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) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Efficient exponential time algorithms for edit distance between unordered trees
• Exact algorithms for computing the tree edit distance between unordered trees
• Fast algorithms for the unit cost editing distance between trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Efficient computation of the tree edit distance
• scientific article; zbMATH DE number 1305084
• Edit distance between unrooted trees in cubic time
• An Optimal Decomposition Algorithm for Tree Edit Distance
• An optimal decomposition algorithm for tree edit distance

Cites work

• A simplified NP-complete satisfiability problem
• A survey on tree edit distance and related problems
• A Visual Explanation of Jensen's Inequality
• An optimal decomposition algorithm for tree edit distance
• Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees
• Approximation and special cases of common subtrees and editing distance
• Exact algorithms for computing the tree edit distance between unordered trees
• Exact and approximate algorithms for unordered tree matching
• Improved approximation of the largest common subtree of two unordered trees of bounded height
• Improved MAX SNP-hard results for finding an edit distance between unordered trees
• On the editing distance between unordered labeled trees
• On tree-constrained matchings and generalizations
• Ordered and Unordered Tree Inclusion
• Some MAX SNP-hard results concerning unordered labeled trees
• The Tree-to-Tree Correction Problem

Cited in

(7)

• A constrained edit distance between unordered labeled trees
• New and improved algorithms for unordered tree inclusion
• Efficient exponential time algorithms for edit distance between unordered trees
• Tractable and intractable variations of unordered tree edit distance
• Edit distance between unrooted trees in cubic time
• scientific article; zbMATH DE number 7561381 (Why is no real title available?)
• Exact algorithms for computing the tree edit distance between unordered trees

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

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