Участник:Lizord/Алгоритм Джонса Плассмана: различия между версиями
Перейти к навигации
Перейти к поиску
Lizord (обсуждение | вклад) м Корректные сноски на литературу |
Lizord (обсуждение | вклад) Добавлено общее описание алгоритма |
||
| Строка 13: | Строка 13: | ||
== Свойства и структура алгоритмов == | == Свойства и структура алгоритмов == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, основанная на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Алгоритм выделения этого подмножества был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref> | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| Строка 31: | Строка 30: | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
== Литература == | == Литература == | ||
Test2 <ref>Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020</ref> | |||
<references /> | <references /> | ||
Версия от 11:39, 16 октября 2025
| Файл: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] |
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Джонса-Плассмана - параллельная версия жадного алгоритма для раскраски графа, основанная на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Алгоритм выделения этого подмножества был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. [1]
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Возможные способы и особенности параллельной реализации алгоритма
Результаты прогонов
Выводы для классов архитектур
Литература
Test2 [2]
- ↑ M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993
- ↑ Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020