Алгоритм проталкивания предпотока

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритмов
3 Литература

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

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

максимальном потоке в транспортной сети

1.2 Математическое описание

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

1.4 Макроструктура алгоритма

1.5 Описание схемы реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Описание ресурса параллелизма алгоритма

Алгоритм основан на локальных операциях и допускает распараллеливание, в том числе на распределённых системах^[1]. Распределение вершин графа по процессорам может производиться на основе результатов предварительного поиска в ширину от вершины-источника потока, так чтобы на каждом процессоре обрабатывалось примерно одинаковое количество вершин одного и того же расстояния от источника.

1.9 Описание входных и выходных данных

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

2 Программная реализация алгоритмов

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

↑ Jiang, Jincheng, and Lixin Wu. “A MPI Parallel Algorithm for the Maximum Flow Problem ,” Geocomputation 2013.

[1] Jiang, Jincheng, and Lixin Wu. “A MPI Parallel Algorithm for the Maximum Flow Problem ,” Geocomputation 2013.

[1]