We present an indexing scheme that supports worst-case optimal (wco) joins over graphs
within compact space. Supporting all possible wco joins using conventional data structures …

Consider the following 2-respecting min-cut problem. Given any weighted graph G and its
spanning tree T, find the minimum cut among the cuts that contain at most two edges in T …

Burrows–Wheeler transform (BWT) is an invertible text transformation that, given a text T of
length n, permutes its symbols according to the lexicographic order of suffixes of T. BWT is …

We consider several types of internal queries, that is, questions about fragments of a given
text specified in constant space by their locations in. Our main result is an optimal data …

We present parallel lightweight algorithms to construct wavelet trees, rank and select
structures, and suffix arrays in a shared-memory setting. The work and depth of our first …

We show that the compressed suffix array and the compressed suffix tree of a string T can be
built in O (n) deterministic time using O (n log σ) bits of space, where n is the string length …

This thesis is devoted to internal queries in texts, which ask to solve classic text-processing
problems for substrings of a given text. More precisely, the task is to preprocess a static …

Abstract The Lempel-Ziv parsing of a string (LZ77 for short) is one of the most important and
widely-used algorithmic tools in data compression and string processing. We show that the …

In the classic longest common substring (LCS) problem, we are given two strings $ S $ and
$ T $, each of length at most $ n $, over an alphabet of size $\sigma $, and we are asked to …

We present an improved wavelet tree construction algorithm and discuss its applications to a
number of rank/select problems for integer keys and strings. Given a string of length n over …