Дискретн. анализ и исслед. опер.,
2013 , том 20, выпуск 3, страницы 26–44
(Mi da730)
Эта публикация цитируется в
12 статьях
Классы субкубических планарных графов, для которых задача о независимом множестве полиномиально разрешима Д. С. Малышев ab a Нац. исслед. университет Высшая школа экономики в Ниж. Новгороде, ул. Б. Печёрская, 25/12, 603155 Н. Новгород, Россия b Нижегородский гос. университет им. Н. И. Лобачевского, пр-т Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия Аннотация:
Доказывается полиномиальная разрешимость задачи о независимом множестве для некоторого семейства классов планарных субкубических графов. Библиогр. 5.
Ключевые слова:
задача о независимом множестве, граничный класс, вычислительная сложность, эффективный алгоритм.
УДК:
519.178 Статья поступила: 10.11.2011
Переработанный вариант: 19.11.2012
© , 2024
Полный текст:
PDF файл (313 kB)