2 citations · 6 across the 9 of their papers we have counts for
9 papers
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…
Association Rule Mining using Maximum Entropy
Rasmus Pagh, Morten Stöckel
Recommendations based on behavioral data may be faced with ambiguous statistical evidence. We consider the case of association rules, relevant e.g.~for query and product recommenda…
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…
The Hardness of the Functional Orientation 2-Color Problem
Søren Bøg, Morten Stöckel, Hjalte Wedel Vildhøj
We consider the Functional Orientation 2-Color problem, which was introduced by Valiant in his seminal paper on holographic algorithms [SIAM J. Comput., 37(5), 2008]. For this deci…