Tractable and intractable variations of unordered tree edit distance

DOI10.1142/S0129054114500154MaRDI QIDQ2929619zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

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

Cites work

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

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)