28 citations · 28 across the 2 of their papers we have counts for
2 papers
cs.DS2017
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)
Karl Bringmann, Paweł Gawrychowski, Shay Mozes +1
The edit distance between two rooted ordered trees with nodes labeled from an alphabet~ is the minimum cost of transforming one tree into the other by a sequence of elementa…
cs.CC2015★ 28 cited
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
Karl Bringmann, Marvin Künnemann
Classic similarity measures of strings are longest common subsequence and Levenshtein distance (i.e., the classic edit distance). A classic similarity measure of curves is dynamic…