2 citations · 6 across the 9 of their papers we have counts for
7 papers · 1 filter
Constructing Light Spanners Deterministically in Near-Linear Time
Stephen Alstrup, Søren Dahlgaard, Arnold Filtser +2
Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [CW18] improved the state-of-the-art for light spann…
New Subquadratic Approximation Algorithms for the Girth
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel
We consider the problem of approximating the girth, , of an unweighted and undirected graph with nodes and edges. A seminal result of Itai and Rodeh [SICOMP'78…
Finding Even Cycles Faster via Capped k-Walks
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel
In this paper, we consider the problem of finding a cycle of length (a ) in an undirected graph with nodes and edges for constant . A classic result…
Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm +2
A graph is an induced universal graph for a family of graphs if every graph in is a vertex-induced subgraph of . For the family of all undirected graphs on verti…
I/O-Efficient Similarity Join
Rasmus Pagh, Ninh Pham, Francesco Silvestri +1
We present an I/O-efficient algorithm for computing similarity joins based on locality-sensitive hashing (LSH). In contrast to the filtering methods commonly suggested our method h…
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…
The Input/Output Complexity of Sparse Matrix Multiplication
Rasmus Pagh, Morten Stöckel
We consider the problem of multiplying sparse matrices (over a semiring) where the number of non-zero entries is larger than main memory. In the classical paper of Hong and Kung (S…