Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)

DOI10.1145/3381878MaRDI QIDQ5888939zbMATH OpenOpenAlexFDO

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

Publication date 26 April 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3381878

zbMATH Keywords

conditional lower boundstring edit distancetree edit distance

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)
• On the hardness of computing the edit distance of shallow trees
• Edit distance between unrooted trees in cubic time
• An Optimal Decomposition Algorithm for Tree Edit Distance
• An optimal decomposition algorithm for tree edit distance

Cited in

(9)

• Improved bounds for rectangular monotone min-plus product and applications
• On the hardness of computing the edit distance of shallow trees
• Weighted edit distance computation: strings, trees, and Dyck
• Faster combinatorial \(k\)-clique algorithms
• Partial permutations comparison, maintenance and applications
• An exact quadratic algorithm for the shortest tree transformation
• Faster algorithms for bounded tree edit distance
• Faster combinatorial k-clique algorithms
• Faster algorithm for bounded tree edit distance in the low-distance regime

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 Q5888939)