35 citations · 50 across the 10 of their papers we have counts for
3 papers · 1 filter
Time-Space Trade-Offs for Longest Common Extensions
Philip Bille, Inge Li Goertz, Benjamin Sach +1
We revisit the longest common extension (LCE) problem, that is, preprocess a string into a compact data structure that supports fast LCE queries. An LCE query takes a pair $(i,…
The Hardness of the Functional Orientation 2-Color Problem
Søren Bøg, Morten Stöckel, Hjalte Wedel Vildhøj
We consider the Functional Orientation 2-Color problem, which was introduced by Valiant in his seminal paper on holographic algorithms [SIAM J. Comput., 37(5), 2008]. For this deci…
Sparse Suffix Tree Construction with Small Space
Philip Bille, Inge Li Gørtz, Tsvi Kopelowitz +2
We consider the problem of constructing a sparse suffix tree (or suffix array) for suffixes of a given text of size , using only words of space during constructio…