scientific article; zbMATH DE number 7375972

DOI10.4230/LIPIcs.ICALP.2018.45zbMath1499.68380arXiv1804.10186MaRDI QIDQ5002720

Bartłomiej Dudek, Paweł Gawrychowski

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1804.10186

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

dynamic programmingtree edit distanceheavy light decomposition

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Data structures (68P05)

Related Items

On the hardness of computing the edit distance of shallow trees

Uses Software

• TED

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey on tree edit distance and related problems
• On the average number of rebalancing operations in weight-balanced trees
• A data structure for dynamic trees
• Approximating tree edit distance through string edit distance
• Decomposition algorithms for the tree edit distance problem
• An optimal decomposition algorithm for tree edit distance
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Compressing and indexing labeled trees, with applications
• Dictionary matching and indexing with errors and don't cares
• Pattern Matching in Trees
• The Tree-to-Tree Correction Problem
• The String-to-String Correction Problem
• Comparison of AESA and LAESA search algorithms using string and tree-edit-distances
• Efficient Computation of the Tree Edit Distance
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• Fast algorithms for the unit cost editing distance between trees
• Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes