Том 20, номер 3, 2013 г., Стр. 26-44

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

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

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

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

Статья поступила 10 ноября 2011 г.
Исправленный вариант — 19 ноября 2012 г.

Литература

[1] Алексеев В. Е., Малышев Д. С. Классы планарных графов с полиномиально разрешимой задачей о независимом множестве // Дискрет. анализ и исслед. операций.  - 2008.  - Т. 15, № 1.  - С. 3–10.

[2] Малышев Д. С. Граничные классы для задачи о независимом множестве в классе планарных графов // Вест. Нижегород. ун-та им. Н. И. Лобачевского.  - 2007.  - № 6.  - С. 165–168.

[3] Alekseev V. E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Appl. Math.  - 2004.  - Vol. 132.  - P. 17–26.

[4] Alekseev V. E., Lozin V. V., Malyshev D. S., Millanic M. The maximum independent set problem in planar graphs // Proc. Mathematical Foundations of Computer Science (Torun, August 25–29, 2008).  - P. 96–107. (Lect. Notes Comput. Sci.; Vol. 5162).

[5] Lozin V. V., Millanic M. Maximum independent sets in graphs of low degree // Proc. ACM-SIAM Symp. Discrete Algorithms (New Orleans, January 7–9, 2007).  - New Orlean: ACM–SIAM, 2007.  - P. 874–880.