|
Дискретный анализ и исследование операций, 2012, том 19, выпуск 3, страницы 58–64
(Mi da690)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Полиномиальная разрешимость задачи о независимом множестве в классе графов без порождённых простых пути и цикла с пятью вершинами и большой клики
Д. С. Малышевab a Нижегородский гос. университет им. Н. И. Лобачевского, Н. Новгород, Россия
b Нац. исслед. университет Высшая школа экономики в Ниж. Новгороде, Н. Новгород, Россия
Аннотация:
Предлагается алгоритм, определяющий число независимости $n$-вершинного графа из класса
$\operatorname{Free}(\{P_5,C_5,K_p\})$ за время $O(n^{p+O(1)})$. Библиогр. 10.
Ключевые слова:
задача о независимом множестве, вычислительная сложность, эффективный алгоритм.
Статья поступила: 01.08.2011
Образец цитирования:
Д. С. Малышев, “Полиномиальная разрешимость задачи о независимом множестве в классе графов без порождённых простых пути и цикла с пятью вершинами и большой клики”, Дискретн. анализ и исслед. опер., 19:3 (2012), 58–64
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da690 https://www.mathnet.ru/rus/da/v19/i3/p58
|
Статистика просмотров: |
Страница аннотации: | 310 | PDF полного текста: | 81 | Список литературы: | 32 | Первая страница: | 1 |
|