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

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

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



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






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


Модел. и анализ информ. систем, 2019, том 26, номер 3, страницы 405–419 (Mi mais687)  

Algorithms

NP-полнота и один полиномиальный подкласс задачи о двухшаговой раскраске графа

Н. С. Медведева, А. В. Смирнов

Ярославский государственный университет им. П.Г. Демидова, ул. Советская, 14, г. Ярославль, 150003 Россия

Аннотация: В данной статье рассматривается задача о двухшаговой раскраске произвольного неориентированного связного графа. Она состоит в нахождении такой раскраски в заданное число цветов, при которой ни одна пара вершин на расстоянии 1 или 2 друг от друга не будет окрашена в одинаковый цвет. Также в работе ставится соответствующая задача распознавания.
Данная задача тесно связана с классической задачей о раскраске графа. В статье рассматривается и обосновывается полиномиальное сведение задач друг к другу. В частности, это позволяет доказать NP-полноту задачи о двухшаговой раскраске. Кроме того, определяются некоторые ее свойства.
Отдельно исследуется задача о двухшаговой раскраске в приложении к прямоугольным графам решетки. Максимальная степень вершины таких графов может принимать значение от 0 до 4, и для каждого возможного случая была определена и обоснована функция двухшаговой раскраски в минимальное число цветов. Полученные функции строятся таким образом, что каждая вершина графа может быть раскрашена независимо от остальных, а время раскраски прямоугольного графа решетки полиномиально при последовательном переборе вершин.

Ключевые слова: двухшаговая раскраска графа, NP-полнота, граф решетки, прямоугольный граф решетки.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-07-00823_а
Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 17-07-00823 А.


DOI: https://doi.org/10.18255/1818-1015-405-419

Полный текст: PDF файл (661 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.174.7
Поступила в редакцию: 14.08.2019
Исправленный вариант: 11.09.2019
Принята в печать:13.09.2019

Образец цитирования: Н. С. Медведева, А. В. Смирнов, “NP-полнота и один полиномиальный подкласс задачи о двухшаговой раскраске графа”, Модел. и анализ информ. систем, 26:3 (2019), 405–419

Цитирование в формате AMSBIB
\RBibitem{MedSmi19}
\by Н.~С.~Медведева, А.~В.~Смирнов
\paper NP-полнота и один полиномиальный подкласс задачи о двухшаговой раскраске графа
\jour Модел. и анализ информ. систем
\yr 2019
\vol 26
\issue 3
\pages 405--419
\mathnet{http://mi.mathnet.ru/mais687}
\crossref{https://doi.org/10.18255/1818-1015-405-419}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais687
  • http://mi.mathnet.ru/rus/mais/v26/i3/p405

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:10
    Полный текст:5
    Литература:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020