14 citations · 22 across the 5 of their papers we have counts for
8 papers
A Turing Kernelization Dichotomy for Structural Parameterizations of -Minor-Free Deletion
Huib Donkers, Bart M. P. Jansen
For a fixed finite family of graphs , the -Minor-Free Deletion problem takes as input a graph and an integer and asks whether there exists a se…
Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers…
Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
Lars Jaffke, Bart M. P. Jansen
The -Coloring problem asks whether the vertices of a graph can be properly colored with colors. Lokshtanov et al. [SODA 2011] showed that -Coloring on graphs with a feedb…
Fine-Grained Complexity Analysis of Two Classic TSP Variants
Mark de Berg, Kevin Buchin, Bart M. P. Jansen +1
We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity. Our first set of results is motivated by the Bitonic TSP problem: gi…
Approximation and Kernelization for Chordal Vertex Deletion
Bart M. P. Jansen, Marcin Pilipczuk
The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel f…
A structural approach to kernels for ILPs: Treewidth and Total Unimodularity
Bart M. P. Jansen, Stefan Kratsch
Kernelization is a theoretical formalization of efficient preprocessing for NP-hard problems. Empirically, preprocessing is highly successful in practice, for example in state-of-t…