3 citations · 7 across the 10 of their papers we have counts for
7 papers · 1 filter
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…
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…
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…