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

16+

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

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

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

Тип статьи	научная статья	Коды УДК	519.17
Страницы	165-168	Ключевые слова

Авторы

Малышев Д.С.

Место работы

Малышев Д.С. Нижегородский госуниверситет им. Н.И. Лобачевского

Аннотация

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

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