Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
verfasst von : Hans L. Bodlaender, Eelko Penninkx, Richard B. Tan
Erschienen in: Algorithms and Computation
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 consider the following problem: given a planar graph
G
= (
V
,
E
) and integer
k
, find if possible at least
k
vertex disjoint cycles in
G
. This problem is known to be NP-complete. In this paper, we give a number of simple data reduction rules. Each rule transforms the input to an equivalent smaller input, and can be carried out in polynomial time. We show that inputs on which no rule can be carried out have size linear in
k
. Thereby we obtain that the
k
-Disjoint Cycles
problem on planar graphs has a kernel of linear size. We also present a parameterized algorithm with a running time of
$O(c^{\sqrt{k}} + n^2)$
.