Gutin, Gregory, Kloks, T., Lee, C.M. and Yeo, Anders (2005) Kernels in planar digraphs. Journal of Computer and System Sciences, 71 (2).
Full text access: Open
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 -time and -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.
This is a Submitted version This version's date is: 2005 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/9793a53c-8a8b-011a-471b-de7501a7878f/5/
Deposited by Research Information System (atira) on 03-Jul-2014 in Royal Holloway Research Online.Last modified on 03-Jul-2014