14 citations · 37 across the 19 of their papers we have counts for
26 papers · 1 filter
New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof +1
The Strongly Connected Steiner Subgraph (SCSS) problem is a well-studied network design problem that asks for a minimum subgraph that strongly connects a given set of terminals. In…
Weighted -Path and Other Problems in Almost Deterministic Time via Dynamic Representative Sets
Jesper Nederlof
We present a data structure that we call a Dynamic Representative Set. In its most basic form, it is given two parameters and allows us to maintain a representation of a…
Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
Andreas Björklund, Petteri Kaski, Tomohiro Koana +1
We show that sufficiently low tensor rank for the balanced tripartitioning tensor for a large enough constan…
A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a -Minor
Carla Groenland, Jesper Nederlof, Tomohiro Koana
We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a termi…
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…
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…