Алгоритм проталкивания предпотока
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм проталкивания предпотока[1] (англ. Push-Relabel Method, или Preflow-Push Method) предназначен для решения задачи о максимальном потоке в транспортной сети. Время работы алгоритма [math]\displaystyle{ O(mn \ln n) }[/math] (при использовании динамических деревьев Тарьяна-Слитора[2][3]).
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Алгоритм основан на локальных операциях и допускает распараллеливание, в том числе на распределённых системах[4]. Распределение вершин графа по процессорам может производиться на основе результатов предварительного поиска в ширину от вершины-источника потока, так чтобы на каждом процессоре обрабатывалось примерно одинаковое количество вершин одного и того же расстояния от источника.
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- C++: Boost Graph Library (функция
push_relabel_max_flow), сложность [math]\displaystyle{ O(n^3) }[/math]. - Python: NetworkX (функция
preflow_push): алгоритм highest-label preflow-push, сложность [math]\displaystyle{ O(n^2\sqrt{m}) }[/math].
Литература
- ↑ Goldberg, Andrew V, and Robert Endre Tarjan. “A New Approach to the Maximum-Flow Problem.” Journal of the ACM 35, no. 4 (October 1988): 921–40. doi:10.1145/48014.61051.
- ↑ Sleator, Daniel D, and Robert Endre Tarjan. “A Data Structure for Dynamic Trees,” STOC'81, 114–22, New York, USA: ACM Press, 1981. doi:10.1145/800076.802464.
- ↑ Sleator, Daniel Dominic, and Robert Endre Tarjan. “Self-Adjusting Binary Search Trees.” Journal of the ACM 32, no. 3 (July 1985): 652–86. doi:10.1145/3828.3835.
- ↑ Jiang, Jincheng, and Lixin Wu. “A MPI Parallel Algorithm for the Maximum Flow Problem ,” Geocomputation 2013.