Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Дискретный анализ и исследование операций, 2018, том 25, выпуск 4, страницы 112–130
DOI: https://doi.org/10.17377/daio.2018.25.617 (Mi da912) 		 
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

О сложности задачи вершинной $3$-раскраски для наследственных классов графов, определённых запретами небольшого размера

Д. В. Сироткинab, Д. С. Малышевab

a Национальный исследовательский университет "Высшая школа экономики", ул. Большая Печёрская, 25/12, 603155, Нижний Новгород, Россия
b Нижегородский гос. университет им. Н. И. Лобачевского, пр. Гагарина, 23, 603950, Нижний Новгород, Россия
PDF полного текста (1771 kB) Список цитирования (5)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.17377/daio.2018.25.617
Аннотация: Задача о $3$-раскраске для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна полная классификация сложности данной задачи для наследственных классов, определяемых тройками запрещённых индуцированных подграфов, каждый с не более чем $5$ вершинами. В настоящей работе рассматриваются четвёрки запрещённых индуцированных фрагментов, каждый с не более чем $5$ вершинами, и для всех соответствующих наследственных классов, кроме трёх, устанавливается вычислительный статус задачи о $3$-раскраске. Для двух из трёх оставшихся случаев доказывается полиномиальная эквивалентность и полиномиальная сводимость к третьему. Ил. 4, библиогр. 20.
Ключевые слова: задача о $3$-раскраске, наследственный класс, вычислительная сложность.
Финансовая поддержка Номер гранта
Российский научный фонд 17-11-01336
Исследование выполнено за счёт гранта Российского научного фонда (проект № 17-11-01336).
Статья поступила: 11.04.2018
Переработанный вариант: 20.05.2018
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2018, Volume 12, Issue 4, Pages 759–769
DOI: https://doi.org/10.1134/S1990478918040166
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.17
Образец цитирования: Д. В. Сироткин, Д. С. Малышев, “О сложности задачи вершинной $3$-раскраски для наследственных классов графов, определённых запретами небольшого размера”, Дискретн. анализ и исслед. опер., 25:4 (2018), 112–130; J. Appl. Industr. Math., 12:4 (2018), 759–769
Цитирование в формате AMSBIB
\RBibitem{SirMal18}
\by Д.~В.~Сироткин, Д.~С.~Малышев
\paper О сложности задачи вершинной $3$-раскраски для наследственных классов графов, определённых запретами небольшого размера
\jour Дискретн. анализ и исслед. опер.
\yr 2018
\vol 25
\issue 4
\pages 112--130
\mathnet{http://mi.mathnet.ru/da912}
\crossref{https://doi.org/10.17377/daio.2018.25.617}
\elib{https://elibrary.ru/item.asp?id=36449714}
\transl
\jour J. Appl. Industr. Math.
\yr 2018
\vol 12
\issue 4
\pages 759--769
\crossref{https://doi.org/10.1134/S1990478918040166}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85058139549}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da912
  • https://www.mathnet.ru/rus/da/v25/i4/p112
    • Эта публикация цитируется в следующих 5 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:215
    PDF полного текста:108
    Список литературы:25
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024