14 citations · 22 across the 11 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DS2017
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…
cs.DS2017
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…