EN|RU

Том 19, номер 3, 2012 г., Стр. 58-64

УДК 519.178
Малышев Д. С. 
Полиномиальная разрешимость задачи о независимом множестве в классе графов без порожденных простых пути и цикла с пятью вершинами и большой клики

Аннотация:
Предлагается алгоритм, определяющий число независимости $n$-вершинного графа из класса $\operatorname{Free}(\{P_5,C_5,K_p\})$ за время $O(n^{p+O(1)})$.
Библиогр. 10.

Ключевые слова: задача о независимом множестве, вычислительная сложность, эффективный алгоритм.

Малышев Дмитрий Сергеевич 1,2
1. Нац. исслед. университет Высшая школа экономики в Ниж. Новгороде,
ул. Б. Печерская, 25/12, 603155 Н. Новгород, Россия
2. Нижегородский гос. университет им. Н. И. Лобачевского,
пр-т Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия
е-mail: dsmalyshev@rambler.ru

Статья поступила 1 августа 2011 г.

 © Институт математики им. С. Л. Соболева, 2015