Faster algorithms for bounded tree edit distance

DOI10.4230/LIPICS.ICALP.2021.12MaRDI QIDQ7241108zbMATH OpenFDO

Authors Shyan S. Akmal, Ce Jin

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

dynamic programmingedit distancetree edit distance

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 1305084 (Why is no real title available?)
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• scientific article; zbMATH DE number 1445367 (Why is no real title available?)
• A faster algorithm computing string edit distances
• A survey on tree edit distance and related problems
• Algorithms for approximate string matching
• Algorithms on Strings, Trees and Sequences
• An \(O(ND)\) difference algorithm and its variations
• An optimal decomposition algorithm for tree edit distance
• Analysis of tree edit distance algorithms
• Approximating edit distance in near-linear time
• Approximating edit distance in truly subquadratic time: quantum and MapReduce
• Approximating edit distance within constant factor in truly sub-quadratic time
• Approximating tree edit distance through string edit distance
• Combinatorial Pattern Matching
• Comparing similar ordered trees in linear-time
• Compressing and indexing labeled trees, with applications
• Constant factor approximations to edit distance on far input pairs in nearly linear time
• Constant-factor approximation of near-linear edit distance in near-linear time
• Decomposition algorithms for the tree edit distance problem
• Edit distance between unrooted trees in cubic time
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Fast algorithms for the unit cost editing distance between trees
• Fast and compact regular expression matching
• Fast string matching with k differences
• Polylogarithmic approximation for edit distance and the asymmetric query complexity
• Shape matching using edit-distance: An implementation
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• The String-to-String Correction Problem
• The Tree-to-Tree Correction Problem
• Tight hardness results for LCS and other sequence similarity measures
• Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)
• \(1+\varepsilon\) approximation of tree edit distance in quadratic time

This page was built for publication: Faster algorithms for bounded tree edit distance

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