- 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/2004Entry Accepted: 06/18/2004Entry Last Modified: 06/18/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.