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

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

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