Kernels in planar digraphs

作者:

Highlights:

摘要

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(n219.1k+n4)-time and O(k36+219.1kk9+n2)-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.

论文关键词:Kernels,Planar digraphs,Fixed-parameter complexity

论文评审过程:Received 16 November 2004, Available online 7 April 2005.

论文官网地址:https://doi.org/10.1016/j.jcss.2005.02.003