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

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

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


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




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

Дискретный анализ и исследование операций, 2023, том 30, выпуск 4, страницы 91–109
DOI: https://doi.org/10.33048/daio.2023.30.758 (Mi da1335) 		 
Полная сложностная дихотомия задачи о рёберной раскраске для всех множеств 8-рёберных запрещённых подграфов

Д. С. Малышевab, О. И. Дугиновc

a Национальный исследовательский университет «Высшая школа экономики», ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
b Нижегородский гос. университет им. Н. И. Лобачевского, пр. Гагарина, 23, 603950 Нижний Новгород, Россия
c Белорусский гос. университет, пр. Независимости, 4, 220030 Минск, Беларусь
PDF полного текста (400 kB)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.33048/daio.2023.30.758
Аннотация: Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых множествами запрещённых подграфов с 7 рёбрами каждый, известен сложностной статус данной задачи. В данной работе получен аналогичный результат для всех множеств 8-рёберных запретов. Ил. 2, библиогр. 38.
Ключевые слова: задача о рёберной раскраске, вычислительная сложность, монотонный класс.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 20-51-04001
Российский научный фонд 21-11-00194
Белорусский республиканский фонд фундаментальных исследований Ф21РМ-001
Разделы 2 и 3 выполнены при финансовой поддержке Российского фонда фундаментальных исследований и Белорусского республиканского фонда фундаментальных исследований (проект № 20–51–04001 (Ф21РМ-001)). Разделы 4 и 5 выполнены при финансовой поддержке Российского научного фонда (проект № 21–11–00194).
Статья поступила: 24.11.2022
Переработанный вариант: 10.06.2023
Принята к публикации: 22.06.2023
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2023, Volume 17, Issue 4, Pages 791–801
DOI: https://doi.org/10.1134/S1990478923040099
Тип публикации: Статья
УДК: 519.17
Образец цитирования: Д. С. Малышев, О. И. Дугинов, “Полная сложностная дихотомия задачи о рёберной раскраске для всех множеств 8-рёберных запрещённых подграфов”, Дискретн. анализ и исслед. опер., 30:4 (2023), 91–109; J. Appl. Industr. Math., 17:4 (2023), 791–801
Цитирование в формате AMSBIB
\RBibitem{MalDug23}
\by Д.~С.~Малышев, О.~И.~Дугинов
\paper Полная сложностная дихотомия задачи о~рёберной раскраске для всех множеств 8-рёберных запрещённых подграфов
\jour Дискретн. анализ и исслед. опер.
\yr 2023
\vol 30
\issue 4
\pages 91--109
\mathnet{http://mi.mathnet.ru/da1335}
\crossref{https://doi.org/10.33048/daio.2023.30.758}
\transl
\jour J. Appl. Industr. Math.
\yr 2023
\vol 17
\issue 4
\pages 791--801
\crossref{https://doi.org/10.1134/S1990478923040099}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da1335
  • https://www.mathnet.ru/rus/da/v30/i4/p91
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:72
    PDF полного текста:21
    Список литературы:18
    Первая страница:2
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024