Том 20, номер 2, 2013 г., Стр. 75-87

УДК 519.178
Малышев Д. С.
Расширяющие операторы для задачи о независимом множестве

Аннотация:
Введено понятие расширяющего оператора для задачи о независимом множестве, являющееся полезным инструментом конструктивного формирования новых случаев эффективной разрешимости этой задачи в семействе наследственных классов графов. Данное понятие применяется к наследственным частям множества $Free(\{P_5,C_5\})$. Именно, доказано, что если для связного графа $G$ задача полиномиально разрешима в классе $Free(\{P_5,C_5,G\})$, то для любого $p$ она остаётся таковой в классе $Free(\{P_5,C_5,G\circ\overline K_2,G\oplus K_{1,p}\})$. Также найдены два новых наследственных подмножества $Free(\{P_5,C_5\})$ с полиномиально разрешимой задачей о независимом множестве, не являющиеся следствием применения указанного оператора.
Библиогр. 22.

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

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

Статья поступила 8 февраля 2012 г.
Исправленный вариант — 20 апреля 2012 г.

Литература

[1] Алексеев В. Е., Таланов В. А. Графы и алгоритмы. Структуры данных. Модели вычислений. - М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006. - 320 c.

[2] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. - М.: Наука, 1990. - 384 c.

[3] Зыков А. А. Основы теории графов. - М.: Наука, 1987. - 383 c.

[4] Малышев Д. С. Полиномиальная разрешимость задачи о независимом множестве в классе графов без порождённых простых пути и цикла с пятью вершинами и большой клики // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 3. - C. 58–64.

[5] Малышев Д. С. Полиномиальная разрешимость задачи о независимом множестве для одного класса графов малого диаметра // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 6. - C. 37–48.

[6] Харари Ф. Теория графов. - М.: Мир, 1982. - 301 c.

[7] 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.

[8] Arbib C., Mosca R. On (P₅, diamond)-free graphs // Discrete Math. - 2002. - Vol. 250. - P. 1–22.

[9] Brandstadt A., Mosca R. On the structure and stability number of P₅- and co-chair-free graphs // Discrete Appl. Math. - 2003. - Vol. 132. - P. 47–65.

[10] Brandstadt A., Le H.-O., Mosca R. Chordal co-gem-free and (P₅, gem)-free graphs have bounded clique-width // Discrete Appl. Math. - 2005. - Vol. 145, N 2. - P. 232.

[11] Bondy A., Murty U. Graph theory. - Heidelberg: Springer-Verl., 2008. - 654 p. (Grad. Texts Math.; Vol. 244).

[12] Chudnovsky M., Robertson N., Seymour P., Thomas R. The strong perfect graph theorem // Ann. Math. - 2002. - Vol. 164. - P. 51–229.

[13] Diestel R. Graph theory. - Heidelberg: Springer-Verl., 2010. - 451 p. (Grad. Texts Math.; Vol. 173).

[14] Gerber M., Lozin V. On the stable set problem in special P₅-free graphs // Discrete Appl. Math. - 2003. - Vol. 125. - P. 215–224.

[15] Grotschel M., Lovasz L., Schrijver A. Geometric algorithms and combinatorial optimization (algorithms and combinatorics) // Berlin: Springer-Verl., 1993. - 564 p.

[16] Lovasz L. A characterization of perfect graphs // J. Comb. Theory, Ser. B. - 1972. - Vol. 13. - P. 95–98.

[17] Lozin V., Mosca R. Maximum independent sets in subclasses of P₅-free graphs // Inf. Process. Lett. - 2009. - Vol. 109, N 6. - P. 319–324.

[18] Mosca R. Polynomial algorithms for the maximum stable set problem on particular classes of P₅-free graphs // Inf. Process. Lett. - 1997. - Vol. 61, N 3. - P. 137–143.

[19] Mosca R. Stable sets in certain P₆-free graphs // Discrete Appl. Math. - 1999. - Vol. 92. - P. 177–191.

[20] Mosca R. Some results on maximum stable sets in certain P₅-free graphs // Discrete Appl. Math. - 2003. - Vol. 132. - P. 175–183.

[21] Mosca R. Some observations on maximum weight stable sets in certain P₅-free graph // Eur. J. Oper. Res. - 2008. - Vol. 184, N 3. - P. 849–859.

[22] Simone C. D., Mosca R. Stable set and clique polytopes of (P₅, gem)-free graphs // Discrete Math. - 2007. - Vol. 307, N 22. - P. 2661–2670.