Распределенный алгоритм раскраски вершин

Ключевые слова и синонимы

Раскраска вершин; распределенные вычисления

Постановка задачи

Задача раскраски вершин принимает на вход неориентированный граф G = (V, E) и вычисляет раскраску вершин, т.е функцию c V [k] от некоторого целого положительного значения k, такую, что смежным вершинам присваиваются разные цвета (иначе говоря, c(u) / c(v) для всех (u, v) 2 E). В задаче (A + 1)-раскраски вершин значение k равно A + 1, где A – максимальная степень входного графа G. В общем случае (A + 1) цветов должно быть достаточно, как показывает пример с кликой. Однако, если граф удовлетворяет определенным свойствам, возможна его раскраска при помощи намного меньшего числа цветов. Нахождение минимально возможного количества цветов представляет собой вычислительно сложную задачу, соответствующие проблемы разрешимости являются NP-полными [ ]. В задаче раскраски Брукса-Визинга цель заключается в нахождении раскрасок, близких к оптимальной.

В данной статье рассматривается модель вычислений в виде синхронной структуры передачи сообщений, используемой в стандартных распределенных вычислениях [11]. В этом случае цель заключается в описании самых простых алгоритмов, которые могут быть легко реализованы на базы этой распределенной модели и при этом демонстрируют высокие показатели в виде количества необходимых шагов выполнения, а также количества используемых цветов. Количество шагов должно быть полилогарифмическим относительно числа вершин графа n, а количество использованных цветов – близким к оптимальному.