Geodesic
NP-completeness of the independent dominating set problem in the class of cubic planar bipartite~graphs
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 65-89

Voir la notice de l'article provenant de la source Math-Net.Ru

It is known that the independent dominating set problem is NP-complete both in the class of cubic planar graphs and in the class of cubic bipartite graphs. The question about the computational complexity of the problem in the intersection of these graph classes has remained open. In this article, we prove that the independent dominating set problem is NP-complete in the class of cubic planar bipartite graphs. Tab. 1, illustr. 7, bibliogr. 19.
Keywords: independent dominating set, cubic graph, planar graph, NP-completeness.
Mots-clés : bipartite graph 
@article{DA_2020_27_2_a3,
     author = {Ya. A. Loverov and Yu. L. Orlovich},
     title = {NP-completeness of the independent dominating set problem in the class of cubic planar bipartite~graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {65--89},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_2_a3/}
}
TY  - JOUR
AU  - Ya. A. Loverov
AU  - Yu. L. Orlovich
TI  - NP-completeness of the independent dominating set problem in the class of cubic planar bipartite~graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 65
EP  - 89
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_2_a3/
LA  - ru
ID  - DA_2020_27_2_a3
ER  - 
%0 Journal Article
%A Ya. A. Loverov
%A Yu. L. Orlovich
%T NP-completeness of the independent dominating set problem in the class of cubic planar bipartite~graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 65-89
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_2_a3/
%G ru
%F DA_2020_27_2_a3
Ya. A. Loverov; Yu. L. Orlovich. NP-completeness of the independent dominating set problem in the class of cubic planar bipartite~graphs. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 65-89. http://geodesic.mathdoc.fr/item/DA_2020_27_2_a3/