Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS seminar by Bart Jansen (TU Eindhoven) : Characterizing the Easy-to-Find Subgraphs from the Viewpoint of Polynomial-Time Algorithms, Kernels, and Turing Kernels

LFCS seminar by Bart Jansen (TU Eindhoven) : Characterizing the Easy-to-Find Subgraphs from the Viewpoint of Polynomial-Time Algorithms, Kernels, and Turing Kernels

— filed under:

What
  • LFCS Seminar
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 vertex-disjoint H-subgraphs 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) polynomial-time solvable,

 

(b) admits a polynomial (many-one) kernel, or (c) admits a polynomial Turing kernel.

Document Actions