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

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

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

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

Задача раскраски вершин принимает на вход неориентированный граф G := (V, E) и вычисляет раскраску вершин, т.е функцию [math]\displaystyle{ c^ V \to [k] }[/math] от некоторого целого положительного значения k, такую, что смежным вершинам присваиваются разные цвета (иначе говоря, [math]\displaystyle{ c(u) \ne c(v) }[/math] для всех [math]\displaystyle{ (u, v) \in E) }[/math]. В задаче [math]\displaystyle{ (\Delta + 1) }[/math]-раскраски вершин значение k равно [math]\displaystyle{ (\Delta + 1) }[/math], где [math]\displaystyle{ \Delta }[/math] – максимальная степень входного графа G. В общем случае [math]\displaystyle{ (\Delta + 1) }[/math] цветов должно быть достаточно, как показывает пример с кликой. Однако, если граф удовлетворяет определенным свойствам, возможна его раскраска при помощи намного меньшего числа цветов. Нахождение минимально возможного количества цветов представляет собой вычислительно сложную задачу, соответствующие проблемы разрешимости являются NP-полными [5]. В задаче раскраски Брукса-Визинга цель заключается в нахождении раскрасок, близких к оптимальной.

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