206 citations · 303 across the 29 of their papers we have counts for
3 papers · 1 filter
Longest Common Extensions in Trees
Philip Bille, Pawel Gawrychowski, Inge Li Goertz +2
The longest common extension (LCE) of two indices in a string is the length of the longest identical substrings starting at these two indices. The LCE problem asks to preprocess a…
Faster Shortest Paths in Dense Distance Graphs, with Applications
Shay Mozes, Yahav Nussbaum, Oren Weimann
We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein,…
Binary Jumbled Pattern Matching via All-Pairs Shortest Paths
Danny Hermelin, Gad M. Landau, Yuri Rabinovich +1
In binary jumbled pattern matching we wish to preprocess a binary string in order to answer queries which ask for a substring of that is of size and has exactly…