TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE

DOI10.1142/S0129054114500154zbMath1303.05203DBLPjournals/ijfcs/YamamotoHK14OpenAlexW2087595659WikidataQ58061118 ScholiaQ58061118MaRDI QIDQ2929619

Yoshiyuki Yamamoto, Tetsuji Kuboyama, Kouichi Hirata

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) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Cites Work

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

Related Items (1)

Tai mapping hierarchy for rooted labeled trees through common subforest

This page was built for publication: TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE