2012 | OriginalPaper | Buchkapitel
A 9k Kernel for Nonseparating Independent Set in Planar Graphs
verfasst von : Łukasz Kowalik, Marcin Mucha
Erschienen in: Graph-Theoretic Concepts in Computer Science
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 study kernelization (a kind of efficient preprocessing) for NP-hard problems on planar graphs. Our main result is a kernel of size at most 9
k
vertices for the
Planar Maximum Nonseparating Independent Set
problem. A direct consequence of this result is that
Planar Connected Vertex Cover
has no kernel with at most 9/8
k
vertices, assuming
P
≠
NP
. We also show a very simple 5
k
-vertices kernel for
Planar Max Leaf
, which results in a lower bound of 5/4
k
vertices for the kernel of
Planar Connected Dominating Set
(also under
P
≠
NP
).