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

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

В алгоритме <math>(\Delta + 1)</math>-раскраски исходная палитра для вершины v задается множеством <math>[\Delta] := \{ 1, ..., \Delta + 1 \}</math> (глобальная настройка) или [d(v) + 1] (где d(v) – степень вершины v) (локальная настройка). Экспериментальные результаты свидетельствуют о том, что (a) наилучшая вероятность пробуждения равна 1, (b) во время выполнения локальная версия палитры оказывается не хуже глобальной, но может обеспечить значительную экономию цветов, (c) венгерская эвристика, применяемая не к случайным числам, а к идентификаторам вершин, дает хорошие результаты.