10 citations · 21 across the 11 of their papers we have counts for
5 papers · 2 filters
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…
Fast Similarity Sketching
Søren Dahlgaard, Mathias Bæk Tejs Langhede, Jakob Bæk Tejs Houen +1
We consider the problem: Given a universe we want a random function mapping subsets into vectors $S(A…
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…
Fast and Compact Exact Distance Oracle for Planar Graphs
Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen
For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an -space distance oracle which answers…