35 citations · 99 across the 47 of their papers we have counts for
7 papers · 1 filter
Space Efficient Construction of Lyndon Arrays in Linear Time
Philip Bille, Jonas Ellert, Johannes Fischer +4
We present the first linear time algorithm to construct the -bit version of the Lyndon array for a string of length using only bits of working space. A simpler varia…
String Indexing with Compressed Patterns
Philip Bille, Inge Li Gørtz, Teresa Anna Steiner
Given a string of length , the classic string indexing problem is to preprocess into a compact data structure that supports efficient subsequent pattern queries. In this…
Partial Sums on the Ultra-Wide Word RAM
Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen
We consider the classic partial sums problem on the ultra-wide word RAM model of computation. This model extends the classic -bit word RAM model with special ultrawords of lengt…
Sparse Regular Expression Matching
Philip Bille, Inge Li Gørtz
A regular expression specifies a set of strings formed by single characters combined with concatenation, union, and Kleene star operators. Given a regular expression and a stri…
Top Tree Compression of Tries
Philip Bille, Inge Li Gørtz, Paweł Gawrychowski +2
We present a compressed representation of tries based on top tree compression [ICALP 2013] that works on a standard, comparison-based, pointer machine model of computation and supp…
Approximation Algorithms for the A Priori TravelingRepairman
Inge Li Gørtz, Viswanath Nagarajan, Fatemeh Navidi
We consider the a priori traveling repairman problem, which is a stochastic version of the classic traveling repairman problem (also called the traveling deliveryman or minimum lat…