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

Основные теоретические результаты, связаны с распределенным <math>(\Delta + 1)</math>-раскрашиванием вершин, вывели Лаби [9] и Джоханссон [7]. Оба показали, как вычислить <math>(\Delta + 1)</math>-раскраску за O(log n) раундов с высокой вероятностью. Для раскраски Брукса-Визинга Ким [8] показал, что если в графе нет квадратов или треугольников, то его можно раскрасить при помощи <math>O(\Delta / log \; \Delta)</math> цветов. Если при этом граф является регулярным с достаточно высокой степенью <math>(\Delta \gg ln n)</math>, для этого случая Грэбл и Панконези [6] показали, как раскрасить его с помощью O(A/log A) цветов за O (log n) раундов. Исчерпывающее обсуждение вероятностных техник достижения подобного раскрашивания см. в работе [10].

Финокки, Панконези и Сильвестри проведели комплексный экспериментальный анализ распределенных алгоритмов раскрашивания вершин, аналогичных упомянутым в этих работах, на разных классах графов. Результаты представлены в разделе «Экспериментальные результаты», а использованные наборы данных – в разделе «Наборы данных».