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

Основные теоретические результаты, связаны с распределенным <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].

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

Раскраска вершин является базовым примитивом многих приложений; классическим примером являются ''задачи планирования'' в присутствии множества попарных ограничений на одновременное выполнение заданий. Например, при составлении расписания занятий в университете два курса, которые ведет один и тот же преподаватель, нельзя поставить на один и тот же временной интервал. Аналогичным образом два курса, предназначенные для одной и той же группы студентов, также не должны конфликтовать друг с другом. Задача определения минимального количества требуемых временных интервалов с учетом этих ограничений может рассматриваться как задача раскраски вершин. Еще одним распространенным приложением является распределение регистров. Задача распределения регистров заключается в присвоении переменных ограниченному числу аппаратных регистров в процессе выполнения программы. Доступ к переменным в регистрах осуществляется намного быстрее, чем к переменным, не хранящимся в регистрах. Однако в большинстве случаев регистров намного меньше, чем переменных, так что приходится одному регистру назначать несколько переменных. Переменные конфликтуют друг с другом, если одна из них используется одновременно перед и после второй в течение короткого периода времени (например, при выполнении подпрограммы). Задача заключается в присвоении переменных, не конфликтующих друг с другом, с целью минимизации использования других видов памяти. Простой подход к ее решению состоит в создании графа, вершины которого представляют переменные, а ребра – конфликты между ними. Раскраска в этом случае представляет бесконфликтное присваивание. Если количество использованных цветов меньше количества регистров, то бесконфликтное присваивание оказывается возможным. Среди современных вариантов применения можно упомянуть присвоение частот мобильным радиостанциям и другие способы использования электромагнитного спектра. В самом простом случае двум клиентам, находящимся достаточно близко друг от друга, необходимо назначить разные частоты, тогда как далекие друг от друга клиенты могут использовать одну частоту. Задача минимизации количества частот также сводится к задаче раскраски вершин. Другим примеры приложений и ссылки см. на странице Майкла Трика, посвященной раскраске [12].

Все проанализированные алгоритмы начинают работу с присвоения исходной палитры цветов каждой вершине и последующего повторения простого раунда итерации:

1. Проснись!: каждая вершина независимо от остальных просыпается с определенной вероятностью участия в раскраске на этом раунде.

2. Попытайся!: каждая вершина независимо от остальных выбирает предварительный цвет из палитры, доступной на этом раунде.

 

4. Накорми голодных!: если в палитре вершины заканчиваются цвета, ей присваиваются новые свежие цвета.

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