LFCS seminar by Bart Jansen (TU Eindhoven) : Characterizing the EasytoFind Subgraphs from the Viewpoint of PolynomialTime Algorithms, Kernels, and Turing Kernels
—
filed under:
LFCS Seminar
What 


When 
Jan 16, 2015 from 11:00 AM to 11:45 AM 
Where  IF 1.16 
Add event to calendar 
vCal iCal 
We study two fundamental problems related to finding subgraphs: given graphs G and H, test whether H is isomorphic to
a subgraph of G, or determine the maximum number of vertexdisjoint Hsubgraphs that can be packed in G. We
investigate these problems when the graph H belongs to a fixed hereditary family F. Our goal is to study which
classes F make the two problems tractable in one of the following senses: (a) (randomized) polynomialtime solvable,
(b) admits a polynomial (manyone) kernel, or (c) admits a polynomial Turing kernel.