121 citations · 416 across the 16 of their papers we have counts for
4 papers · 1 filter
Kernelization of Packing Problems
Holger Dell, Dániel Marx
Kernelization algorithms are polynomial-time reductions from a problem to itself that guarantee their output to have a size not exceeding some bound. For example, d-Set Matching fo…
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell +1
The Strong Exponential Time Hypothesis and the OV-conjecture are two popular hardness assumptions used to prove a plethora of lower bounds, especially in the realm of polynomial-ti…
Extensor-Coding
Cornelius Brand, Holger Dell, Thore Husfeldt
We devise an algorithm that approximately computes the number of paths of length in a given directed graph with vertices up to a multiplicative error of …
Lovász Meets Weisfeiler and Leman
Holger Dell, Martin Grohe, Gaurav Rattan
In this paper, we relate a beautiful theory by Lovász with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k-dimensio…