Том 19, номер 3, 2012 г., Стр. 58-64

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

Аннотация:
Предлагается алгоритм, определяющий число независимости $n$-вершинного графа из класса $\operatorname{Free}(\{P_5,C_5,K_p\})$ за время $O(n^{p+O(1)})$.
Библиогр. 10.

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

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

Статья поступила 1 августа 2011 г.

Литература

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

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

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

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

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

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

[7] Mosca R. Stable sets in certain $P_6$-free graphs // Discrete Appl. Math. — 1999. — Vol. 92. — P. 177–191.

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

[9] Mosca R. Some observations on maximum weight stable sets in certain $P$ // Eur. J. Oper. Res. — 2008. — Vol. 184, N 3. — P. 849–859.

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