Name
Abstract | ||
|---|---|---|
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 is an element of N, we have d(u, v), d(v,, u) >= k; it is 1- absorbent if for every u is an element of V(D) - N there exists v is an element of 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.7151/dmgt.1727 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
kernel,3-kernel,NP-completeness,multipartite tournament,cyclically 3-partite digraphs,k-quasi-transitive digraph | Kernel (linear algebra),Discrete mathematics,Combinatorics,Vertex (geometry),Mathematics,Digraph,Computational complexity theory | Journal |
Volume | Issue | ISSN |
34 | 1 | 1234-3099 |
Citations | PageRank | References |
3 | 0.45 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pavol Hell | 1 | 2638 | 288.75 |
| César Hernández-Cruz | 2 | 33 | 10.41 |