Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
From MaRDI portal
Publication:1168729
DOI10.1016/0166-218X(81)90003-2zbMath0493.68040MaRDI QIDQ1168729
Publication date: 1981
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
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
This page was built for publication: Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
