Участник: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], которое раскрашивается параллельно.
   
3. После этого полагаем [math]\displaystyle{ V' = V'\;\backslash\;I }[/math]. Алгоритм работает, пока [math]\displaystyle{ V' \neq \emptyset }[/math].

Подмножество независимых вершин [math]\displaystyle{ I }[/math] выделяется следующим образом :

Положим [math]\displaystyle{ I = \emptyset, V' = V, G' = G }[/math]. Повторяем следующие шаги, пока [math]\displaystyle{ G' \neq \emptyset }[/math]:

1. [math]\displaystyle{ I = I \cup I' }[/math]
2. [math]\displaystyle{ X = I' \cup N(I') }[/math]
3. [math]\displaystyle{ V' = V' \;\backslash\; X }[/math]
4. [math]\displaystyle{ G' = G(V') }[/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] итераций.

Литература

Test2