Campus Event Calendar
Event Entry
What and Who
Polynomial-Time Data Reduction and Problem Kernels
Jiong Guo
Friedrich-Schiller-Universität Jena
Talk
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 10 March 2009
10:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
To solve NP-hard problems, polynomial-time preprocessing is a natural and promising approach. Preprocessing is based on data reduction techniques that take a problem's input instance and try to perform a reduction to a smaller, equivalent problem kernel.
In this talk, I will give a brief introduction to data reduction and problem kernels and review some recent developments in this field, in particular, a linear kernelization for Cluster Editing and a general framework for deriving linear kernels for planar graph problems.
Contact
Conny Liegl
302-70150
--email hidden
passcode not visible
logged in users only
Conny Liegl, 03/09/2009 13:40 -- Created document.