Распределенный алгоритм раскраски вершин
Ключевые слова и синонимы
Раскраска вершин; распределенные вычисления
Постановка задачи
Задача раскраски вершин принимает на вход неориентированный граф G := (V, E) и вычисляет раскраску вершин, т.е функцию [math]\displaystyle{ c^ V \to [k] }[/math] от некоторого целого положительного значения k, такую, что смежным вершинам присваиваются разные цвета (иначе говоря, [math]\displaystyle{ c(u) \ne c(v) }[/math] для всех [math]\displaystyle{ (u, v) \in E) }[/math]. В задаче [math]\displaystyle{ (\Delta + 1) }[/math]-раскраски вершин значение k равно [math]\displaystyle{ (\Delta + 1) }[/math], где [math]\displaystyle{ \Delta }[/math] – максимальная степень входного графа G. В общем случае [math]\displaystyle{ (\Delta + 1) }[/math] цветов должно быть достаточно, как показывает пример с кликой. Однако, если граф удовлетворяет определенным свойствам, возможна его раскраска при помощи намного меньшего числа цветов. Нахождение минимально возможного количества цветов представляет собой вычислительно сложную задачу, соответствующие проблемы разрешимости являются NP-полными [5]. В задаче раскраски Брукса-Визинга цель заключается в нахождении раскрасок, близких к оптимальной.
В данной статье рассматривается модель вычислений в виде синхронной структуры передачи сообщений, используемой в стандартных распределенных вычислениях [11]. В этом случае цель заключается в описании самых простых алгоритмов, которые могут быть легко реализованы на базы этой распределенной модели и при этом являются эффективными с точки зрения количества необходимых шагов выполнения, а также качественными – с точки зрения количества используемых цветов. Для достижения достаточной эффективности количество шагов должно быть полилогарифмическим относительно числа вершин графа n, а для достижения достаточного качества количество использованных цветов должно быть близким к оптимальному.
Основные результаты
Основные теоретические результаты, связаны с распределенным [math]\displaystyle{ (\Delta + 1) }[/math]-раскрашиванием вершин, вывели Лаби [9] и Джоханссон [7]. Оба показали, как вычислить [math]\displaystyle{ (\Delta + 1) }[/math]-раскраску за O(log n) раундов с высокой вероятностью. Для раскраски Брукса-Визинга Ким [8] показал, что если в графе нет квадратов или треугольников, то его можно раскрасить при помощи [math]\displaystyle{ O(\Delta / log \; \Delta) }[/math] цветов. Если при этом граф является регулярным с достаточно высокой степенью [math]\displaystyle{ (\Delta \gg ln n) }[/math], для этого случая Грэбл и Панконези [6] показали, как раскрасить его с помощью O(A/log A) цветов за O (log n) раундов. Исчерпывающее обсуждение вероятностных техник достижения подобного раскрашивания см. в работе [10].
Финокки, Панконези и Сильвестри проведели комплексный экспериментальный анализ распределенных алгоритмов раскрашивания вершин, аналогичных упомянутым в этих работах, на разных классах графов. Результаты представлены в разделе «Экспериментальные результаты», а использованные наборы данных – в разделе «Наборы данных».
Применение
Раскраска вершин является базовым примитивом многих приложений; классическим примером являются задачи планирования в присутствии множества попарных ограничений на одновременное выполнение заданий. Например, при составлении расписания занятий в университете два курса, которые ведет один и тот же преподаватель, нельзя поставить на один и тот же временной интервал. Аналогичным образом два курса, предназначенные для одной и той же группы студентов, также не должны конфликтовать друг с другом. Задача определения минимального количества требуемых временных интервалов с учетом этих ограничений может рассматриваться как задача раскраски вершин. Еще одним распространенным приложением является распределение регистров. Задача распределения регистров заключается в присвоении переменных ограниченному числу аппаратных регистров в процессе выполнения программы. Доступ к переменным в регистрах осуществляется намного быстрее, чем к переменным, не хранящимся в регистрах. Однако в большинстве случаев регистров намного меньше, чем переменных, так что приходится одному регистру назначать несколько переменных. Переменные конфликтуют друг с другом, если одна из них используется одновременно перед и после второй в течение короткого периода времени (например, при выполнении подпрограммы). Задача заключается в присвоении переменных, не конфликтующих друг с другом, с целью минимизации использования других видов памяти. Простой подход к ее решению состоит в создании графа, вершины которого представляют переменные, а ребра – конфликты между ними. Раскраска в этом случае представляет бесконфликтное присваивание. Если количество использованных цветов меньше количества регистров, то бесконфликтное присваивание оказывается возможным. Среди современных вариантов применения можно упомянуть присвоение частот мобильным радиостанциям и другие способы использования электромагнитного спектра. В самом простом случае двум клиентам, находящимся достаточно близко друг от друга, необходимо назначить разные частоты, тогда как далекие друг от друга клиенты могут использовать одну частоту. Задача минимизации количества частот также сводится к задаче раскраски вершин. Другим примеры приложений и ссылки см. на странице Майкла Трика, посвященной раскраске [12].