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

16+

Название статьи

О СЛОЖНОСТИ ЗАДАЧИ О ДОМИНИРУЮЩЕМ МНОЖЕСТВЕ В ПОДКЛАССАХ КЛАССА РАСЩЕПЛЯЕМЫХ ГРАФОВ

Номер журнала	6
Дата выпуска	2010

Тип статьи	научная статья	Коды УДК	519.17
Страницы	143-147	Ключевые слова	задача о доминирующем множестве, расщепляемый граф, вычислительная сложность

Авторы

Малышев Дмитрий СергеевичЗамараев Виктор АндреевичМокеев Дмитрий Борисович

Место работы

Малышев Дмитрий Сергеевич Нижегородский госуниверситет им. Н.И. Лобачевского, Нижегородский филиал Государственного университета - Высшей школы экономики
Замараев Виктор Андреевич Нижегородский госуниверситет им. Н.И. Лобачевского
Мокеев Дмитрий Борисович Нижегородский госуниверситет им. Н.И. Лобачевского

Аннотация

Известно, что задача о доминирующем множестве в классе расщепляемых графов NP-полна. Изучается влияние степеней некоторых вершин таких графов на вычислительную сложность этой задачи.

Загрузить статью

Библиографический список

1 . Alekseev V.E., Korobitsyn D.V., Lozin V.V. Boundary classes of graphs for the dominating set problem // Rutcor Research Report. 2002. № 25. P. 1-10.
2 . Alekseev V.E., Boliac R., Korobitsyn D.V.,Lozin V.V. NP-hard graph problems and boundary classes of graphs // Theoretical Computer Science. 2007. V. 389. P. 219-236.