Участник:Lizord/Алгоритм Джонса Плассмана

Файл:Warning sign font awesome.svg

Данная страница в настоящее время активно редактируется участником Lizord (обсуждение). Пожалуйста, не вносите в неё никаких изменений до тех пор, пока не исчезнет это объявление. В противном случае могут возникнуть конфликты редактирования.

Основные авторы описания: Демаков М. А.

Алгоритм Джонса-Плассмана
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(V + E) }[/math]
Объём входных данных	[math]\displaystyle{ 8|E| }[/math]
Объём выходных данных	[math]\displaystyle{ V }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O(\frac{log(V)}{log log(V)}) }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O(log(V)) }[/math]

Свойства и структура алгоритмов

Общее описание алгоритма

Алгоритм Джонса-Плассмана - параллельная версия жадного алгоритма для раскраски графа, основанная на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Алгоритм выделения этого подмножества был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей.

Математическое описание алгоритма

Исходные данные: граф [math]\displaystyle{ G = G(V, E) }[/math], где [math]\displaystyle{ V }[/math] - множество вершин, а [math]\displaystyle{ E }[/math] - множество ребёр.
Вычисляемые данные: вектор цветов [math]\displaystyle{ c = \{c_i\} }[/math] размерности [math]\displaystyle{ |V| }[/math]

Для раскраски графа, необходимо проделать следующие шаги:

1. Обозначим множество нераскрашенных вершин как [math]\displaystyle{ V' = V }[/math].
   
2. На каждой итерации будем выделять максимальное независимое подмножество вершин [math]\displaystyle{ I \subset V' }[/math], которое раскрашивается параллельно.
   1. Для каждой вершины [math]\displaystyle{ v_i \in V' }[/math] назначается уникальная случайная метка [math]\displaystyle{ p(v_i) }[/math]
   2. [math]\displaystyle{ v_i \in I \Leftrightarrow p(v) \gt p(w), \forall w \in adj(v_i) }[/math]
3. После этого полагаем [math]\displaystyle{ V' = V'\;\backslash\;I }[/math]. Алгоритм работает, пока [math]\displaystyle{ V' \neq \emptyset }[/math].

Для раскраски вершины [math]\displaystyle{ v_i \in I }[/math] необходимо назначить ей цвет [math]\displaystyle{ c_i }[/math] такой, что [math]\displaystyle{ c_i \notin N_c(v_i) }[/math], где [math]\displaystyle{ N_c(v_i) }[/math] - цвета вершин, соседних для [math]\displaystyle{ v_i }[/math]. Это можно сделать последовательным перебором, это займёт в худшем случае [math]\displaystyle{ deg(v_i) }[/math] итераций.

Вычислительное ядро алгоритма

Вычислительным ядром алгоритма является выделение из множества нераскрашенных вершин графа максимального независимого подмножества, которое впоследствии раскрашивается параллельно.

Входные и выходные данные алгоритма

Входные данные: Граф [math]\displaystyle{ G = G(V, E) }[/math]
Объём входных данных: [math]\displaystyle{ 8|E| }[/math] если граф представлен списком связности.</math>

Выходные данные: Вектор [math]\displaystyle{ c = {c_i} }[/math], содержащий итоговые цвета вершин.
Объём выходных данных: [math]\displaystyle{ |V| }[/math]

Литература

Test2