PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 1 | 167-185
Tytuł artykułu

On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
34
Numer
1
Strony
167-185
Opis fizyczny
Daty
wydano
2014-02-01
online
2014-02-14
Twórcy
autor
  • School of Computing Science Simon Fraser University Burnaby, B.C., Canada V5A 1S6, pavol@sfu.ca
  • School of Computing Science Simon Fraser University Burnaby, B.C., Canada V5A 1S6, chernand@sfu.ca
Bibliografia
  • [1] J. Bang-Jensen and G. Gutin, Digraphs (Springer-Verlag, Berlin Heidelberg New York, 2002).
  • [2] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141-161. doi:10.1002/jgt.3190200205[Crossref]
  • [3] C. Berge, Graphs (North-Holland, Amsterdam, 1985).
  • [4] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27-31. doi:10.1016/0012-365X(90)90346-J[Crossref]
  • [5] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, Berlin Heidelberg New York, 2008).
  • [6] V. Chvátal, On the computational complexity of finding a kernel , Technical Report Centre de Recherches Mathématiques, Université de Montréal CRM-300 (1973).
  • [7] A.S. Fraenkel, Planar kernel and Grundy with d ≤ 3, d+ ≤ 2, d− ≤ 2 are NP- complete, Discrete Appl. Math. 3 (1981) 257-262. doi:10.1016/0166-218X(81)90003-2[Crossref]
  • [8] H. Galeana-Sánchez, I.A. Goldfeder and I. Urrutia, On the structure of 3-quasi-transitive digraphs, Discrete Math. 310 (2010) 2495-2498. doi:10.1016/j.disc.2010.06.008[Crossref][WoS]
  • [9] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in multipartite tournaments, AKCE Int. J. Graphs Comb. 8 (2011) 181-198.
  • [10] H. Galeana-Sánchez and C. Hernández-Cruz, On the existence of k-kernels digraphs and in weighted digraphs, AKCE Int. J. Graphs Comb. 7 (2010) 201-215.
  • [11] H. Galeana-Sánchez and C. Hernández-Cruz, Cyclically k-partite digraphs and k- kernels, Discuss. Math. Graph Theory 31 (2011) 63-78. doi:10.7151/dmgt.1530[Crossref]
  • [12] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in generalizations of transitive digraphs, Discuss. Math. Graph Theory 31 (2011) 293-312. doi:10.7151/dmgt.1546[Crossref]
  • [13] H. Galeana-Sánchez, C. Hernández-Cruz and M.A. Juárez-Camacho, On the existence and number of (k+1)-kings in k-quasi-transitive digraphs, Discrete Math. 313 (2013) 2582-2591.[WoS][Crossref]
  • [14] C. Hernández-Cruz and H. Galeana-Sánchez, k-kernels in k-transitive and k-quasi- transitive digraphs, Discrete Math. 312 (2012) 2522-2530. doi:10.1016/j.disc.2012.05.005[WoS][Crossref]
  • [15] M. Kwaśnik, A. W loch and I. W loch, Some remarks about (k, l)-kernels in directed and undirected graphs, Discuss. Math. 13 (1993) 29-37.
  • [16] M. Richardson, On weakly ordered systems, Bull. Amer. Math. Soc. 52(2) (1946) 113-116. doi:10.1090/S0002-9904-1946-08518-3[Crossref]
  • [17] A. Sánchez-Flores, A counterexample to a generalization of Richardson’s theorem, Discrete Math. 65 (1987) 319-320. doi:10.1016/0012-365X(87)90064-1 [Crossref]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1727
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.