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

В раскраске Брукса-Визинга исходная палитра задается значением [d(v)/s], где s – ''коэффициент стягивания''. Экспериментальные результаты свидетельствуют о том, что оптимальную равномерную эффективность демонстрирует алгоритм, у которого вероятность пробуждения равна 1, а конфликты разрешаются при помощи венгерской эвристики. Это касается как времени выполнения, так и числа использованных цветов. Реалистически полезные значения s относятся к диапазону от 4 до 6, что приводит к <math>\Delta / s</math>-раскраске. Эффективность согласно критерию времени выполнения превосходна; даже графы с тысячами вершин удается раскрасить за 20-30 раундов. По сравнению с последовательными алгоритмами такие алгоритмы используют в 2-3 раза больше цветов, но работают намного быстрее.