35 citations · 44 across the 5 of their papers we have counts for
5 papers
Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz +1
Given a string , the \emph{compressed indexing problem} is to preprocess into a compressed representation that supports fast \emph{substring queries}. The goal is to use lit…
Longest Common Extensions in Sublinear Space
Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen +2
The longest common extension problem (LCE problem) is to construct a data structure for an input string of length that supports LCE queries. Such a query returns the…
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…