121 citations · 181 across the 38 of their papers we have counts for
7 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…
Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters
Carla Groenland, Isja Mannens, Jesper Nederlof +2
A homomorphism from a graph to a graph is an edge-preserving mapping from to . In the graph homomorphism problem, denoted by , the graph is fixed a…
A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
Jesper Nederlof, Céline M. F. Swennenhuis, Karol Węgrzycki
In a classical scheduling problem, we are given a set of jobs of unit length along with precedence constraints, and the goal is to find a schedule of these jobs on identica…
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…
Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
Andreas Björklund, Petteri Kaski, Jesper Nederlof
Finding a Hamiltonian cycle in a given graph is computationally challenging, and in general remains so even when one is further given one Hamiltonian cycle in the graph and asked t…
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
Parinya Chalermsook, Fedor Fomin, Thekla Hamm +3
We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a ``non-trivial'' approximation…