Сборники трудов ИСП РАН


Приближенный алгоритм для хроматической раскраски двудольных графов за полиномиальное в среднем время

A.С. Асратян (Линчёпингский университет, Швеция), Н.Н. Кузюрин (ИСП РАН, Москва)

Аннотация

Известно что если P≠NP то задача аппроксимации суммарной раскраски двудольных графов не может быть осуществлена в полиномиальное время с точностью 1+ε для некоторой константы ε. Мы предлагаем для сколь угодно малого  ε">0"  приближенный алгоритм для данной проблемы который работает за полиномиальное в среднем время.

Ключевые слова

проблема хроматической раскраски, двудольные графы, полиномиальное в среднем время

Издание

Труды Института системного программирования РАН, том 27, вып. 5, 2015, стр. 191-198.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2015-27(5)-11

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома