On the complexity of the 3-kernel problem in some classes of digraphs
From MaRDI portal
Publication:2442275
DOI10.7151/dmgt.1727zbMath1292.05124MaRDI QIDQ2442275
César Hernández-Cruz, Pavol Hell
Publication date: 2 April 2014
Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7151/dmgt.1727
NP-completeness; kernel; multipartite tournament; 3-kernel; cyclically 3-partite digraphs; k-quasi-transitive digraph
05C20: Directed graphs (digraphs), tournaments
Related Items
\((H, k)\)-reachability in \(H\)-arc-colored digraphs, Some results on 4-transitive digraphs, A new generalization of kernels in digraphs, On the existence of 3- and 4-kernels in digraphs, On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs, On the existence of \((k,l)\)-kernels in infinite digraphs: a survey, Quasi-Transitive Digraphs and Their Extensions, Domination in Digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the existence and number of (\(k+1\))-kings in \(k\)-quasi-transitive digraphs
- \(k\)-kernels in \(k\)-transitive and \(k\)-quasi-transitive digraphs
- On the existence of \(k\)-kernels in digraphs and in weighted digraphs
- \(k\)-kernels in multipartite tournaments
- On the structure of strong 3-quasi-transitive digraphs
- A counterexample to a generalization of Richardson's theorem
- Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
- Recent problems and results about kernels in directed graphs
- k-kernels in generalizations of transitive digraphs
- Cyclically k-partite digraphs and k-kernels
- Quasi‐transitive digraphs
- On weakly ordered systems