Tractable and intractable variations of unordered tree edit distance

DOI10.1142/S0129054114500154zbMATH Open1303.05203DBLPjournals/ijfcs/YamamotoHK14OpenAlexW2087595659WikidataQ58061118 ScholiaQ58061118MaRDI QIDQ2929619FDOQ2929619

Authors: Yoshiyuki Yamamoto, Kouichi Hirata, Tetsuji Kuboyama 

Publication date: 14 November 2014

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054114500154

Recommendations

• Exact algorithms for computing the tree edit distance between unordered trees
• A constrained edit distance between unordered labeled trees
• Alignment of trees -- an alternative to tree edit
• On the editing distance between unordered labeled trees
• Efficient exponential-time algorithms for edit distance between unordered trees

zbMATH Keywords

tree edit distanceunordered treevariations of Tai mappingvariations of tree edit distance

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07) Distance in graphs (05C12)

Cites Work

• Optimization, approximation, and complexity classes
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Faster Scaling Algorithms for Network Problems
• The Tree-to-Tree Correction Problem
• Some MAX SNP-hard results concerning unordered labeled trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• On the editing distance between unordered labeled trees
• ON THE EDITING DISTANCE BETWEEN UNDIRECTED ACYCLIC GRAPHS
• The tree-to-tree editing problem
• A constrained edit distance between unordered labeled trees
• A Tree-to-Tree Distance and Its Application to Cluster Analysis
• Finding similar consensus between trees: An algorithm and a distance hierarchy
• 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

Cited In (4)

• Distinguishing Local and Global Edits for Their Simultaneous Propagation in a Uniform Framework
• Improved MAX SNP-hard results for finding an edit distance between unordered trees
• Tai mapping hierarchy for rooted labeled trees through common subforest
• Improved methods for computing distances between unordered trees using integer programming

This page was built for publication: Tractable and intractable variations of unordered tree edit distance

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