1 citations · 1 across the 2 of their papers we have counts for
8 papers
Independence number of intersection graphs of axis-parallel segments
Marco Caoduro, Jana Cslovjecsek, Michał Pilipczuk +1
We prove that for any triangle-free intersection graph of axis-parallel segments in the plane, the independence number of this graph is at least . W…
Bounding generalized coloring numbers of planar graphs using coin models
Jesper Nederlof, Michał Pilipczuk, Karol Węgrzycki
We study Koebe orderings of planar graphs: vertex orderings obtained by modelling the graph as the intersection graph of pairwise internally-disjoint discs in the plane, and orderi…
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…
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…