14 citations · 37 across the 19 of their papers we have counts for
5 papers · 1 filter
Parameterized Algorithms for Covering by Arithmetic Progressions
Ivan Bliznets, Jesper Nederlof, Krisztina Szilágyi
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two pro…
Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
Jesper Nederlof, Krisztina Szilágyi
In this paper we investigate the parameterized complexity of the task of counting and detecting occurrences of small patterns in unit disk graphs: Given an -vertex unit disk gra…
A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth
Isja Mannens, Jesper Nederlof
We give a fine-grained classification of evaluating the Tutte polynomial on all integer points on graphs with small treewidth and cutwidth. Specifically, we show for any…
Isolation schemes for problems on decomposable graphs
Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis +1
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87] provides a self-reduction scheme that allows one to assume that a given instance of a problem has a unique…
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…