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

Материал из WEGA
Версия от 22:44, 2 сентября 2019; Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Раскраска вершин; распределенные вычисления == Постановка…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

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

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

Задача раскраски вершин принимает на вход неориентированный граф 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, а количество использованных цветов – близким к оптимальному.

Основные результаты