EN|RU

Том 19, номер 4, 2012 г., Стр. 66-72

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

Аннотация:
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов ${\mathcal Free}(\{P_5,C_5\})$. Именно, доказывается, что если эта задача полиномиально разрешима в классе ${\mathcal Free}(\{P_5,C_5,G\})$, то для любого графа $H$, который может быть индуктивно получен из $G$ применением к текущему графу сложения с $K_1$ или умножения на $K_1$, эта задача имеет тот же вычислительный статус в классе ${\mathcal Free}(\{P_5,C_5,H\})$.
Библиогр. 10.

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

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

Статья поступила 19 октября 2011 г.

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