2009 | OriginalPaper | Buchkapitel
Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
verfasst von : Geevarghese Philip, Venkatesh Raman, Somnath Sikdar
Erschienen in: Algorithms - ESA 2009
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show that the
k
-Dominating Set
problem is fixed parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude
K
i
,
j
as a subgraph, for any fixed
i
,
j
≥ 1. This strictly includes every class of graphs for which this problem has been previously shown to have FPT algorithms and/or polynomial kernels. In particular, our result implies that the problem restricted to bounded-degenerate graphs has a polynomial kernel, solving an open problem posed by Alon and Gutner in [3].