Kernels in planar digraphs

Gregory Gutin (gutincs.rhul.ac.uk)
Ton Kloks (gutinonetel.net.uk)
Chuan Min Lee (gutinonetel.net.uk)
Anders Yeo (anderscs.rhul.ac.uk)

Abstract: A set $S$ of vertices in a digraph $D=(V,A)$ is a kernel if $S$ is independent and every vertex in $V-S$ has an out-neighbor in $S$. We show that there exist $O(n2^{19.1 \sqrt{k}}+n^4)$-time and $O(2^{19.1 \sqrt{k}} k^9 + n^2)$-time algorithms for checking whether a planar digraph $D$ of order $n$ has a kernel with at most $k$ vertices. Moreover, if $D$ has a kernel of size at most $k$, the algorithms find such a kernel of minimal size.

Keywords: digraphs, kernels, FPT

Category 1: Combinatorial Optimization (Graphs and Matroids )

Citation:

Download: [PDF]

Entry Submitted: 06/18/2004
Entry Accepted: 06/18/2004
Entry Last Modified: 06/18/2004

Modify/Update this entry