RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2012, том 19, выпуск 3, страницы 58–64 (Mi da690)

Эта публикация цитируется в 1 статье

Полиномиальная разрешимость задачи о независимом множестве в классе графов без порождённых простых пути и цикла с пятью вершинами и большой клики

Д. С. Малышевab

a Нижегородский гос. университет им. Н. И. Лобачевского, Н. Новгород, Россия
b Нац. исслед. университет Высшая школа экономики в Ниж. Новгороде, Н. Новгород, Россия

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

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

УДК: 519.178

Статья поступила: 01.08.2011



Реферативные базы данных:


© МИАН, 2024