Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees

DOI10.1007/978-3-642-21458-5_34zbMath1339.68105OpenAlexW2287267492WikidataQ58061259 ScholiaQ58061259MaRDI QIDQ3011871

Yoshiyuki Yamamoto, Kouichi Hirata, Tetsuji Kuboyama

Publication date: 29 June 2011

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21458-5_34

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items

Tai mapping hierarchy for rooted labeled trees through common subforest ⋮ TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE ⋮ Efficient exponential-time algorithms for edit distance between unordered trees ⋮ On the complexity of finding a largest common subtree of bounded degree

Cites Work

• Unnamed Item
• A survey on tree edit distance and related problems
• Alignment of trees -- an alternative to tree edit
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Optimization, approximation, and complexity classes
• On the editing distance between unordered labeled trees
• Some MAX SNP-hard results concerning unordered labeled trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• The Tree-to-Tree Correction Problem
• ON THE EDITING DISTANCE BETWEEN UNDIRECTED ACYCLIC GRAPHS
• Exact and approximate algorithms for unordered tree matching