206 citations · 303 across the 29 of their papers we have counts for
3 papers · 1 filter
The Fine-Grained Complexity of Episode Matching
Philip Bille, Inge Li Gørtz, Shay Mozes +2
Given two strings and , the Episode Matching problem is to find the shortest substring of that contains as a subsequence. The best known upper bound for this problem…
An Almost Optimal Edit Distance Oracle
Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes +1
We consider the problem of preprocessing two strings and , of lengths and , respectively, in order to be able to efficiently answer the following queries: Given posit…
Fault-Tolerant Distance Labeling for Planar Graphs
Aviv Bar-Natan, Panagiotis Charalampopoulos, Paweł Gawrychowski +2
In fault-tolerant distance labeling we wish to assign short labels to the vertices of a graph such that from the labels of any three vertices we can infer the -to-$v…