Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)

MaRDI QIDQ4607965zbMATH OpenFDO

Authors Karl Bringmann, Paweł Gawrychowski, Shay Mozes, Oren Weimann

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1703.08940, http://dl.acm.org/citation.cfm?id=3175347

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Recommendations

• Edit distance between unrooted trees in cubic time
• An Optimal Decomposition Algorithm for Tree Edit Distance
• An optimal decomposition algorithm for tree edit distance
• \(1+\varepsilon\) approximation of tree edit distance in quadratic time
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems

Cited in

(12)

• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• scientific article; zbMATH DE number 7561381 (Why is no real title available?)
• Edit distance between unrooted trees in cubic time
• Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)
• \(1+\varepsilon\) approximation of tree edit distance in quadratic time
• New and improved algorithms for unordered tree inclusion
• Fine-grained non-interactive key-exchange without idealized assumptions
• Improved bounds for rectangular monotone min-plus product and applications
• Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
• Inexact tree pattern matching with 1-degree edit distance using finite automata
• On the hardness of computing the edit distance of shallow trees
• Algebraic dynamic programming on trees

This page was built for publication: Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)

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