On the hardness of computing the edit distance of shallow trees

DOI10.1007/978-3-031-20643-6_21zbMath1525.68037OpenAlexW4312993098MaRDI QIDQ6111592

Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, Oren Weimann

Publication date: 4 August 2023

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-20643-6_21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey on tree edit distance and related problems
• Comparing similar ordered trees in linear-time
• The tree-to-tree editing problem
• Decomposition algorithms for the tree edit distance problem
• Improved bounds for rectangular monotone min-plus product and applications
• An optimal decomposition algorithm for tree edit distance
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Compressing and indexing labeled trees, with applications
• Pattern Matching in Trees
• The Tree-to-Tree Correction Problem
• Algorithms on Strings, Trees and Sequences
• The String-to-String Correction Problem
• Comparison of AESA and LAESA search algorithms using string and tree-edit-distances
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Efficient Computation of the Tree Edit Distance
• 1+ ε approximation of tree edit distance in quadratic time
• Approximating Tree Edit Distance Through String Edit Distance
• Fast algorithms for the unit cost editing distance between trees
• Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes