35 citations · 99 across the 47 of their papers we have counts for
62 papers
Improved Regular Expression Matching with Simple Backreferences
Philip Bille, Inge Li Gørtz, Rikke Schjeldrup Jessen
A regular expression with backreferences (rewb) specifies a set of strings formed by characters combined with concatenation, union, star operators, and backreferences. A backrefere…
Tighter Bounds for Wheeler Determinization
Philip Bille, Inge Li Gørtz, Máximo Pérez-López +1
Given a Wheeler NFA , the Wheeler determinization problem is to construct a Wheeler DFA that accepts the same language as . We use the notat…
Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries
Philip Bille, Johannes Fischer, Inge Li Gørtz +1
We study the data structure version of the \emph{element distinctness problem}: preprocess an array of elements from an alphabet of size to answer \textsc{All-Distinct} que…
Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm
Christian Møller Mikkelstrup, Anders Bjorholm Dahl, Philip Bille +2
Computing a minimum - cut in a graph is a solution to a wide range of computer vision problems, and is often done using the Boykov-Kolmogorov (BK) algorithm. In this paper, w…
An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju +5
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph that is realized by sampling each edge independently with s…
How many users have been here for a long time? Efficient solutions for counting long aggregated visits
Peyman Afshani, Rezaul Chowdhury, Inge Li Gørtz +3
This paper addresses the Counting Long Aggregated Visits problem, which is defined as follows. We are given users and regions, where each user spends some time visiting som…