Campus Event Calendar
Event Entry
What and Who
Cuts in Graphs - Algorithms and Combinatorics
Matthias Mnich
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 24 February 2012
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Finding cuts of maximum size is one of one of Karp's 21 NP-complete problems, and approximation algorithms for this problem have inspired many fundamental directions in approximation algorithm design. However, very little is known about the parameterized complexity of the Max-Cut problem. We present new combinatorial and fixed-parameter tractability results for Max-Cut and related problems. Some of our results answer long-standing open questions from parameterized complexity or asymptotically improve earlier results.
Contact
Matthias Mnich
--email hidden
passcode not visible
logged in users only
Matthias Mnich, 02/20/2012 11:46 -- Created document.