Распределенный алгоритм раскраски вершин: различия между версиями

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

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