Решение задачи о максимальном потоке через сеть (оптимизация временных затрат)
Автор: Русакова Ольга Леонидовна, Черноземова Н.А.
Журнал: Вестник Пермского университета. Серия: Математика. Механика. Информатика @vestnik-psu-mmi
Рубрика: Механика. Математическое моделирование
Статья в выпуске: 2 (2), 2010 года.
Бесплатный доступ
Рассмотрен один из вариантов решения практической задачи определения неучтенных потерь нефти в сети нефтепровода при жестких ограничениях на время счета. Она сводится к задаче поиска максимального потока через сеть. Приводятся результаты исследования параллельной реализации алгоритма Голдберга "Проталкивание предпотока" с целью оптимизации временных затрат на получение решения.
Поиск, максимальный поток, сеть, алгоритм голдберга, параллельная реализация
Короткий адрес: https://sciup.org/14729660
IDR: 14729660
Список литературы Решение задачи о максимальном потоке через сеть (оптимизация временных затрат)
- Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
- Липский В. Комбинаторика для программистов/пер. с польского. М.: Мир, 1988.
- Goldberg A.V., Tarjan R.E. A New Approach to the Maximum Flow Problem//J. Assoc. Comput. Mach., 35: 921-940, 1988.
- Goldberg A.V., Rao S. Length functions for flow computations. Technical report #97-055, NEC Research Institute, 1997.
- Деменев А.Г. Параллельные вычислительные системы: учеб.-метод. пос./Перм. ун-т. Пермь, 2007.
- Деменев А.Г. Программирование для параллельных вычислительных систем: учеб.-метод. пос./Перм. ун-т. Пермь, 2007.
