1 citations · 1 across the 3 of their papers we have counts for
7 papers · 1 filter
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…
Separator Theorem and Algorithms for Planar Hyperbolic Graphs
Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen +2
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incompa…
Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
Jesper Nederlof, Karol Węgrzycki
We present an time and space randomized algorithm for solving worst-case Subset Sum instances with integers. Th…
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…
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Karl Bringmann, Marvin Künnemann, Karol Węgrzycki
Zwick's -approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time , where i…
Equal-Subset-Sum Faster Than the Meet-in-the-Middle
Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz +1
In the Equal-Subset-Sum problem, we are given a set of integers and the problem is to decide if there exist two disjoint nonempty subsets , whose elements…