Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete

DOI10.1016/0166-218X(81)90003-2zbMath0493.68040MaRDI QIDQ1168729

Aviezri S. Fraenkel

Publication date: 1981

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completenessplanar digraphgrundy numberingplanar kernel

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items (30)

Kernels by monochromatic paths and color-perfect digraphs ⋮ Richardson's theorem in \(H\)-coloured digraphs ⋮ Some results on the structure of kernel-perfect and critical kernel-imperfect digraphs ⋮ H-kernels by walks ⋮ A Polyhedral Description of Kernels ⋮ Kernels in graphs with a clique-cutset ⋮ On Kernels of Graphs and Solutions of Games: A Synopsis Based on Relations and Fixpoints ⋮ Algorithmic aspects of small quasi-kernels ⋮ Richardson's theorem in quasi-transitive and pre-transitive digraphs ⋮ On the kernel and related problems in interval digraphs ⋮ Alternating kernels ⋮ Finding kernels or solving SAT ⋮ Partitioning vertices into in- and out-dominating sets in digraphs ⋮ Perfect graphs, kernels, and cores of cooperative games ⋮ Out-degree reducing partitions of digraphs ⋮ On the complexity of the 3-kernel problem in some classes of digraphs ⋮ A new generalization of kernels in digraphs ⋮ Kernels in planar digraphs ⋮ Perfect graphs with polynomially computable kernels ⋮ Strong kernel number in certain oriented cycle extension of graphs ⋮ Domination in Digraphs ⋮ Computational properties of argument systems satisfying graph-theoretic constraints ⋮ Stable matching with uncertain pairwise preferences ⋮ Vertex- and edge-minimal and locally minimal graphs ⋮ On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs ⋮ On the \(k\)-domination number of digraphs ⋮ Quasi-Transitive Digraphs and Their Extensions ⋮ Towards the small quasi-kernel conjecture ⋮ Some operations preserving the existence of kernels ⋮ An extension of Richardson's theorem in m-colored digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of problems in games, graphs and algebraic equations
• Some simplified NP-complete graph problems
• Planar Formulae and Their Uses
• A remark on a problem of Harary

This page was built for publication: Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete