Аннотация:
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. В данной работе доказываем полиномиальную разрешимость этой задачи для субкубических планарных графов, не содержащих порождённого дерева, получаемого отождествлением концов трёх путей длины 3, 3 и 2 соответственно. Библиогр. 10.
Ключевые слова:
задача о независимом множестве, редукция графов, эффективный алгоритм.
Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований (проекты 16–31–60008-мол а дк, 17–01–00710-а), гранта Президента РФ MK-4819.2016.1 и лаборатории алгоритмов и технологий анализа сетевых структур НИУ ВШЭ.
Статья поступила: 25.07.2016 Переработанный вариант: 12.01.2017
Образец цитирования:
Д. С. Малышев, Д. В. Сироткин, “Полиномиальная разрешимость задачи о независимом множестве в одном классе субкубических планарных графов”, Дискретн. анализ и исслед. опер., 24:3 (2017), 35–60; J. Appl. Industr. Math., 11:3 (2017), 400–414
\RBibitem{MalSir17}
\by Д.~С.~Малышев, Д.~В.~Сироткин
\paper Полиномиальная разрешимость задачи о независимом множестве в~одном классе субкубических планарных графов
\jour Дискретн. анализ и исслед. опер.
\yr 2017
\vol 24
\issue 3
\pages 35--60
\mathnet{http://mi.mathnet.ru/da874}
\crossref{https://doi.org/10.17377/daio.2017.24.549}
\elib{https://elibrary.ru/item.asp?id=29869482}
\transl
\jour J. Appl. Industr. Math.
\yr 2017
\vol 11
\issue 3
\pages 400--414
\crossref{https://doi.org/10.1134/S1990478917030115}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85028556389}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da874
https://www.mathnet.ru/rus/da/v24/i3/p35
Эта публикация цитируется в следующих 3 статьяx:
С. В. Сорочан, “Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными триодами”, Дискретн. анализ и исслед. опер., 30:1 (2023), 85–109
S. V. Sorochan, “New Cases of Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Triodes”, J. Appl. Ind. Math., 17:1 (2023), 185
В. Е. Алексеев, С. В. Сорочан, “Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными путями”, Дискретн. анализ и исслед. опер., 25:2 (2018), 5–18; V. E. Alekseev, S. V. Sorochan, “New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths”, J. Appl. Industr. Math., 12:2 (2018), 213–219
Цитирование в формате AMSBIB
Обратная связь: