4 citations · 4 across the 4 of their papers we have counts for
4 papers
Sublinear Time Shortest Path in Expander Graphs
Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen +1
Computing a shortest path between two nodes in an undirected unweighted graph is among the most basic algorithmic tasks. Breadth first search solves this problem in linear time, wh…
A Dichotomy for Regular Expression Membership Testing
Karl Bringmann, Allan Grønlund, Kasper Green Larsen
We study regular expression membership testing: Given a regular expression of size and a string of size , decide whether the string is in the language described by the regul…
Towards Tight Lower Bounds for Range Reporting on the RAM
Allan Grønlund, Kasper Green Larsen
In the orthogonal range reporting problem, we are to preprocess a set of points with integer coordinates on a grid. The goal is to support reporting all points…
Approximate Range Emptiness in Constant Time and Optimal Space
Mayank Goswami, Allan Grønlund, Kasper Green Larsen +1
This paper studies the \emph{-approximate range emptiness} problem, where the task is to represent a set of points from and answer emptiness…