Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки

16+

Title of Article

ON THE COMPLEXITY OF DOMINATING SET PROBLEM FOR SUBCLASSES OF SPLIT GRAPH CLASS

Issue	6
Date	2010

Article type	scientific article	UDC	519.17
Pages	143-147	Keywords	dominating set problem, split graph, computational complexity

Authors

Malyshev Dmitriy SergeevichNizhegorodskiy gosuniversitet im. N.I. Lobachevskogo, Nizhegorodskiy filial Gosudarstvennogo universiteta - Vysshey shkoly ekonomiki
Zamaraev Viktor AndreevichNizhegorodskiy gosuniversitet im. N.I. Lobachevskogo
Mokeev Dmitriy BorisovichNizhegorodskiy gosuniversitet im. N.I. Lobachevskogo

Abstract

The dominating set problem is known to be NP-complete in the split graph class. The influence of degrees of some vertices of such graphs on the computational complexity of the problem is studied.

File (in Russian)