3 citations · 7 across the 10 of their papers we have counts for
12 papers
Steiner Tree Parameterized by Multiway Cut and Even Less
Bart M. P. Jansen, Céline M. F. Swennenhuis
In the Steiner Tree problem we are given an undirected edge-weighted graph as input, along with a set of vertices called terminals. The task is to output a minimum-weight conne…
Scheduling jobs that change over time
Roel Lambers, Rudi Pendavingh, Frits Spieksma +1
We consider a 1-machine scheduling problem where the temperature of a job rises during processing, and cools down when not being processed according to given linear heating and coo…
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…
Makespan Scheduling of Unit Jobs with Precedence Constraints in time
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 identical…
On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem
Isja Mannens, Jesper Nederlof, Céline Swennenhuis +1
We study a variant of Min Cost Flow in which the flow needs to be connected. Specifically, in the Connected Flow problem one is given a directed graph , along with a set of dema…
Parameterized Complexities of Dominating and Independent Set Reconfiguration
Hans L. Bodlaender, Carla Groenland, Céline M. F. Swennenhuis
We settle the parameterized complexities of several variants of independent set reconfiguration and dominating set reconfiguration, parameterized by the number of tokens. We show t…
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…
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
Hans L. Bodlaender, Carla Groenland, Jesper Nederlof +1
Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time and space (…
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis +1
In the Bin Packing problem one is given items with weights and bins with capacities . The goal is to find a partition of the items into set…
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis +1
For many algorithmic problems on graphs of treewidth , a standard dynamic programming approach gives an algorithm with time and space complexity $2^{\mathcal{O}(t)}\cdot n^{\mat…
Parameterized Complexity of Partial Scheduling
Jesper Nederlof, Céline Swennenhuis
We study a natural variant of scheduling that we call \emph{partial scheduling}: In this variant an instance of a scheduling problem along with an integer is given and one seek…
Parallel Machine Scheduling with a Single Resource per Job
T. Janssen, C. Swennenhuis, A. Bitar +5
We study the problem of scheduling jobs on parallel machines minimizing the total completion time, with each job using exactly one resource. First, we derive fundamental properties…