Д. С. Малышев, “Классы субкубических планарных графов, для которых задача о независимом множестве полиномиально разрешима”, Дискретн. анализ и исслед. опер., 2013, том 20, выпуск 3,страницы 26

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

Классы субкубических планарных графов, для которых задача о независимом множестве полиномиально разрешима

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

^a Нац. исслед. университет Высшая школа экономики в Ниж. Новгороде, ул. Б. Печёрская, 25/12, 603155 Н. Новгород, Россия
^b Нижегородский гос. университет им. Н. И. Лобачевского, пр-т Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия

Аннотация: Доказывается полиномиальная разрешимость задачи о независимом множестве для некоторого семейства классов планарных субкубических графов. Библиогр. 5.

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

УДК: 519.178

Статья поступила: 10.11.2011
Переработанный вариант: 19.11.2012