BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Domination When the Stars Are Out – An algorithmization of Chudn
 ovsky’s and Seymour’s Structure Theorem for Claw-Free Graphs - Matthia
 s Mnich\, International Computer Science Institute\, Berkeley
DTSTART:20110408T130000Z
DTEND:20110408T140000Z
UID:TALK29230@talks.cam.ac.uk
CONTACT:Bjarki Holm
DESCRIPTION:We algorithmize the recent structural characterization for cla
 w-free graphs by Chudnovsky and Seymour. Building on this result\, we show
  that Dominating Set on claw-free graphs is (i) fixed-parameter tractable 
 and (ii) even possesses a polynomial kernel. To complement these results\,
  we establish that Dominating Set is not fixed-parameter tractable on the 
 slightly larger class of graphs that exclude K_{1\,4} as an induced subgra
 ph. Our results provide a dichotomy for Dominating Set in K_{1\,L}-free gr
 aphs and show that the problem is fixed-parameter tractable if and only if
  L <= 3. Finally\, we show that our algorithmization can also be used to s
 how that the related Connected Dominating Set problem is fixed-parameter t
 ractable on claw-free graphs.  \n\n(joint work with Danny Hermelin\, Erik 
 Jan van Leeuwen and Gerhard Woeginger – Max Planck Institut fur Informat
 ik\, University of Bergen/Norway\, and TU Eindhoven/Netherlands) 
LOCATION:Room FW11\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR