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

DOI10.1145/3381878OpenAlexW3040166286MaRDI QIDQ5888939

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

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

tree edit distancestring edit distanceconditional lower bound

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (1)

Improved bounds for rectangular monotone min-plus product and applications

This page was built for publication: Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)