114 citations · 385 across the 36 of their papers we have counts for
Showing 2014 · cs.DSShow all
2 papers · 2 filters
cs.DS2014
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
Bart M. P. Jansen, Dániel Marx
We study two fundamental problems related to finding subgraphs: (1) given graphs G and H, Subgraph Test asks if H is isomorphic to a subgraph of G, (2) given graphs G, H, and an in…
cs.DS2014★ 52 cited
Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes
Bart M. P. Jansen
The NP-complete -Path problem asks whether a given undirected graph has a (simple) path of length at least . We prove that -Path has polynomial-size Turing kernels when re…