Главная страница
russian   english
16+
<< back

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 Sergeevich
Nizhegorodskiy gosuniversitet im. N.I. Lobachevskogo, Nizhegorodskiy filial Gosudarstvennogo universiteta - Vysshey shkoly ekonomiki

Zamaraev Viktor Andreevich
Nizhegorodskiy gosuniversitet im. N.I. Lobachevskogo

Mokeev Dmitriy Borisovich
Nizhegorodskiy 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)