10 citations · 22 across the 14 of their papers we have counts for
4 papers · 1 filter
Sublinear Distance Labeling
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen +1
A distance labeling scheme labels the nodes of a graph with binary strings such that, given the labels of any two nodes, one can determine the distance in the graph between the…
Longest Common Extensions in Sublinear Space
Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen +2
The longest common extension problem (LCE problem) is to construct a data structure for an input string of length that supports LCE queries. Such a query returns the…
Optimal induced universal graphs and adjacency labeling for trees
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen
We show that there exists a graph with nodes, where any forest of nodes is a node-induced subgraph of . Furthermore, for constant arboricity , the result impli…
Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence
Mathias Bæk Tejs Knudsen, Morten Stöckel
Randomized algorithms and data structures are often analyzed under the assumption of access to a perfect source of randomness. The most fundamental metric used to measure how "rand…