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

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

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


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




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

Дискретная математика, 2016, том 28, выпуск 2, страницы 44–50
DOI: https://doi.org/10.4213/dm1367 (Mi dm1367) 		 
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)

Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов

Д. С. Малышевab

a Национальный исследовательский университет «Высшая школа экономики»
b Нижегородский государственный университет им. Н. И. Лобачевского
PDF полного текста (390 kB) Список цитирования (6)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/dm1367
Аннотация: Класс графов называется монотонным, если он замкнут относительно удалений вершин и рёбер. Любой такой класс может быть задан запрещёнными подграфами. Хроматическим индексом графа называется наименьшее количество цветов, необходимое для такого раскрашивания его рёбер, что любые два соседних ребра имеют разные цвета. В статье получена полная классификация сложности задачи о хроматическом индексе для всех монотонных классов, определяемых запрещёнными подграфами, каждый из которых имеет не более 6 рёбер или не более 7 вершин.
Работа выполнена при поддержке Российского Фонда Фундаментальных Исследований, проект № 16-31-60008-мол_а_дк, гранта Президента РФ МК-4819.2016.1, лаборатории алгоритмов и технологий анализа сетевых структур НИУ ВШЭ.
Ключевые слова: вычислительная сложность, задача о хроматическом индексе, эффективный алгоритм.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 16-31-60008-мол_а_дк
Министерство образования и науки Российской Федерации МК-4819.2016.1
Работа выполнена при поддержке Российского Фонда Фундаментальных Исследований, проект № 16-31-60008-мол_а_дк, гранта Президента РФ МК-4819.2016.1, лаборатории алгоритмов и технологий анализа сетевых структур НИУ ВШЭ.
Статья поступила: 11.01.2016
Англоязычная версия:
Discrete Mathematics and Applications, 2017, Volume 27, Issue 2, Pages 97–101
DOI: https://doi.org/10.1515/dma-2017-0011
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.174
Образец цитирования: Д. С. Малышев, “Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов”, Дискрет. матем., 28:2 (2016), 44–50; Discrete Math. Appl., 27:2 (2017), 97–101
Цитирование в формате AMSBIB
\RBibitem{Mal16}
\by Д.~С.~Малышев
\paper Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов
\jour Дискрет. матем.
\yr 2016
\vol 28
\issue 2
\pages 44--50
\mathnet{http://mi.mathnet.ru/dm1367}
\crossref{https://doi.org/10.4213/dm1367}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3559790}
\elib{https://elibrary.ru/item.asp?id=26414201}
\transl
\jour Discrete Math. Appl.
\yr 2017
\vol 27
\issue 2
\pages 97--101
\crossref{https://doi.org/10.1515/dma-2017-0011}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000403472300004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85018449158}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/dm1367
  • https://doi.org/10.4213/dm1367
  • https://www.mathnet.ru/rus/dm/v28/i2/p44
    • Эта публикация цитируется в следующих 6 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретная математика
    Статистика просмотров:
    Страница аннотации:401
    PDF полного текста:67
    Список литературы:39
    Первая страница:22
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024