Kernels in planar digraphs

Gregory Gutin; Ton Kloks; Chuan Min Lee; Anders Yeo

doi:10.1016/j.jcss.2005.02.003

Kernels in planar digraphs

Gregory Gutin
, Ton Kloks
, Chuan Min Lee
, Anders Yeo

Royal Holloway University of London
University of Lethbridge
National Chung Cheng University

Research output: Contribution to journal › Article › peer-review

16 Citations (Scopus)

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(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.

Original language	English
Pages (from-to)	174-184
Number of pages	11
Journal	Journal of Computer and System Sciences
Volume	71
Issue number	2
DOIs	https://doi.org/10.1016/j.jcss.2005.02.003
Publication status	Published - Aug 2005
Externally published	Yes

Keywords

Fixed-parameter complexity
Kernels
Planar digraphs

ASJC Scopus subject areas

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.jcss.2005.02.003

Cite this

@article{f2146f75ac5a4d10afe752f3fc197971,

title = "Kernels in planar digraphs",

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(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.",

keywords = "Fixed-parameter complexity, Kernels, Planar digraphs",

author = "Gregory Gutin and Ton Kloks and Lee, \{Chuan Min\} and Anders Yeo",

year = "2005",

month = aug,

doi = "10.1016/j.jcss.2005.02.003",

language = "English",

volume = "71",

pages = "174--184",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Kernels in planar digraphs

AU - Gutin, Gregory

AU - Kloks, Ton

AU - Lee, Chuan Min

AU - Yeo, Anders

PY - 2005/8

Y1 - 2005/8

N2 - 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.

AB - 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.

KW - Fixed-parameter complexity

KW - Kernels

KW - Planar digraphs

UR - https://www.scopus.com/pages/publications/21144449690

U2 - 10.1016/j.jcss.2005.02.003

DO - 10.1016/j.jcss.2005.02.003

M3 - Article

AN - SCOPUS:21144449690

SN - 0022-0000

VL - 71

SP - 174

EP - 184

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

Kernels in planar digraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this