35 citations · 99 across the 47 of their papers we have counts for
7 papers · 2 filters
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…
Mergeable Dictionaries With Shifts
Philip Bille, Mikko Berggren Etienne, Inge Li Gørtz
We revisit the mergeable dictionaries with shift problem, where the goal is to maintain a family of sets subject to search, split, merge, make-set, and shift operations. The search…