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

zbMATH Open1403.68368arXiv1703.08940MaRDI QIDQ4607965FDOQ4607965

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

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

Mathematics Subject Classification ID

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

Cited In (11)

• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Title not available (Why is that?)
• 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
• 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)