Domination when the stars are out

D. Hermelin, M. Mnich, E.J. Leeuwen, van, G.J. Woeginger

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

18 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

We algorithmize the recent structural characterization for claw-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 subgraph. Our results provide a dichotomy for Dominating Set in K 1,l-free graphs 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 show that the related Connected Dominating Set problem is fixed-parameter tractable on claw-free graphs.
Originele taal-2Engels
TitelAutomata, Languages and Programming (38th International Colloquium, ICALP 2011, Zürich, Switzerland, July 4-8, 2011. Proceedings, Part I)
RedacteurenL. Aceto, M. Henzinger, J. Sgall
Plaats van productieBerlin
UitgeverijSpringer
Pagina's462-473
ISBN van geprinte versie978-3-642-22005-0
DOI's
StatusGepubliceerd - 2011

Publicatie series

NaamLecture Notes in Computer Science
Volume6755
ISSN van geprinte versie0302-9743

Vingerafdruk

Duik in de onderzoeksthema's van 'Domination when the stars are out'. Samen vormen ze een unieke vingerafdruk.

Citeer dit