- Tytuł:
- On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
- Autorzy:
-
Hell, Pavol
Hernández-Cruz, César - Powiązania:
- https://bibliotekanauki.pl/articles/30147225.pdf
- Data publikacji:
- 2014-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
kernel
3-kernel
NP-completeness
multipartite tournament
cyclically 3-partite digraphs
k-quasi-transitive digraph - Opis:
- Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in quite restricted families of digraphs. In this paper we analyze the computational complexity of the corresponding 3-kernel problem, restricted to three natural families of digraphs. As a consequence of one of our main results we prove that the kernel problem remains NP-complete when restricted to 3-colorable digraphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2014, 34, 1; 167-185
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł