Исследование стационарных и динамических потоков в сетях без ограничений и с ограничениями на достижимость тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Водолазов, Николай Николаевич

• Водолазов, Николай Николаевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Водолазов, Николай Николаевич

ВВЕДЕНИЕ.

Глава 1. ОБЗОР ЛИТЕРАТУРЫ. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ.

1.1. Задача поиска максимального потока на графе.

1.2. Обзор задач о динамическом потоке.

1.3. Основные подходы к решению задач на графах с нестандартной достижимостью.

Глава 2. ПОТОК НА ГРАФАХ С НЕСТАНДАРТНОЙ

ДОСТИЖИМОСТЬЮ.

2.1. Определение потока в сети с ограничениями на достижимость.

2.2. Поток в сети с барьерными ограничениями на достижимость.

2.3. Обобщение алгоритма поиска максимального потока на графах со связанными дугами.

2.4. ЫР-полнота задачи нахождения максимального целочисленного потока с ограничениями на достижимость.

Глава 3. ДИНАМИЧЕСКИЕ ПОТОКИ В СЕТЯХ.

3.1. Основные определения.

3.2. Ограничение на величину динамического потока.

3.3. Нахождение максимального всплеска на графе.

3.4. Нахождение потока, имеющего максимальный объем.

Введение диссертации (часть автореферата) на тему «Исследование стационарных и динамических потоков в сетях без ограничений и с ограничениями на достижимость»

Актуальность темы исследований. Стремительные перемены, происходящие в мире, ставят перед наукой много вопросов, связанных с перспективами развития экономики, ее ближайшим и отдаленным будущим. В современных условиях повышение эффективности перемещения товаров от производителя к потребителям, информации между компьютерами через электронные сети по всему миру с меньшими затратами является актуальной проблемой. Выбор оптимальных решений транспортных задач в контексте глобализации современного мира требует научного поиска в этой области.

Известно, что теория графов предоставляет необходимую основу для решения задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных сетей и многих других.

Если приписать каждой дуге ориентированного графа поток некоторого вещества, граф становится удобной моделью при исследовании целого ряда проблем в транспорте, связи и других областях, связанных с движением товаров, информации и людей.

Задача поиска потока максимальной величины и двойственная ей задача поиска минимального разреза - это классические комбинаторные задачи с многочисленными научными и практическими приложениями. Например, определение максимальной интенсивности транспортного потока между двумя пунктами и определение части сети дорог, которая насыщена и образует «узкое место».

Обычно поток не перемещается по сети мгновенно, а требуется определенное время для прохождения по каждой дуге. В частности, когда принимается решение о маршрутизации пакета в одной части сети, результат может быть заметен в другой части сети спустя некоторое время. Следовательно, не только величина передающегося потока, но и время, требуемое для передачи, играет важную роль.

Изменение потока с течением времени - это важная особенность задачи о потоке в сети, возникающая в различных приложениях, таких как управление дорожным и воздушным движением, информационные сети (в том числе Интернет) и финансовые потоки. В таких приложениях величины потока по дугам непостоянны и могут изменяться с течением времени.

Указанные выше стороны потока в сети не охватываются классическими моделями стационарного потока. В таких случаях появляется необходимость в рассмотрении потока, изменяющегося с течением времени, т.е. динамического потока, который включает временное измерение и поэтому является более удобным инструментом моделирования многих практических задач.

В последнее время получило развитие исследование сетей с ограничениями на достижимость, которые являются средством для моделирования производственных процессов и телекоммуникационных сетей. Обычная (стандартная) достижимость предполагает, что допустимыми являются все возможные пути на графе. Нестандартная достижимость предполагает, что допустимыми являются не все возможные пути на графе, а только те, которые удовлетворяют некоторым дополнительным условиям. В зависимости от того, какие условия рассматриваются, возникают разные виды нестандартной достижимости.

В этой связи нужны новые подходы к решению задач с различными видами нестандартной достижимости, основанные на современных достижениях науки и техники и передовой практики, что и определяет актуальность настоящего диссертационного исследования.

Степень разработанности проблемы. Исследованиями в области теории графов занимались многие ученые как в нашей стране, так и за рубежом. Выдающимся достижением алгоритмической теории графов следует назвать теорию потоков в сетях, созданную JI.P. Фордом и Д.Р. Фалкерсоном [42, 53]. Дальнейшее развитие эта теория получила в работах Е.А. Диница [11, 50], Дж. Р. Эдмондса и P.M. Карпа [51], A.B. Карзанова [65], A.B. Голдберга [59, 61] и многих других. Задачи о нестандартной достижимости рассмотрены в работах

Я.М. Ерусалимского [14, 15, 19, 26, 31], Е.О. Басанговой [3-5], А.Г. Петросяна [18, 25, 34-36], В.А. Скороходова [13, 17, 22, 24, 39-41] и других.

Необходимость проведения теоретического анализа и целесообразность обобщения отечественного и зарубежного опыта решения задач нового класса дают основание диссертанту осуществлять собственный научный поиск.

Объект и предмет исследования. Объектом исследования являются графы с нестандартной достижимостью и динамические графы, в том числе с нестандартной достижимостью. Предметом диссертационного исследования являются решения задач поиска максимального потока в графах с нестандартной достижимостью и максимального динамического потока.

Цель исследования. Целью исследования является поиск алгоритмов для решения задач о максимальном потоке на графах с дополнительными ограничениями на достижимость, а также построение алгоритмов для поиска максимального всплеска в сети и нахождения максимального объема сети.

Научная новизна диссертационного исследования заключается в доказательстве ЫР-полноты задачи поиска максимального потока на графах с некоторыми видами нестандартной достижимости, построении полиномиальных алгоритмов для задачи поиска максимального потока для других видов нестандартной достижимости, введении определения максимального всплеска и максимального объема сети, построении алгоритмов для их нахождения.

Научная и практическая значимость. Работа носит теоретический характер. Полученные в диссертации результаты могут найти применение в решении задач логистики и маршрутизации для электронных сетей.

Достоверность и обоснованность полученных в диссертационном исследовании теоретических результатов обеспечивается корректным применением математического аппарата, строгим математическим обоснованием предложенных методов и алгоритмов.

Основные положения диссертационного исследования, выносимые на защиту:

1. Доказана ЫР-полнота задачи нахождения максимального потока для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к >2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимо сть.

2. Построены полиномиальные алгоритмы нахождения максимального потока для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к = 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями.

3. Исследована задача нахождения максимального всплеска в сети и приведен алгоритм ее решения.

4. Исследована задача нахождения максимального объема сети и приведен алгоритм ее решения.

Представление материалов диссертационной работы на конференциях. Основные результаты работы докладывались соискателем на Воронежской весенней математической школе «Понтрягинские чтения» в 2008, 2009 и 2010 годах.

Публикации. Содержание диссертационного исследования и его результаты изложены в публикациях автора. По теме диссертации опубликовано 7 научных работ ([7-10, 12, 20, 21]), 2 работы написаны без соавторов.

Структура диссертационной работы. Диссертация состоит из введения, трех глав, заключения и библиографического списка. Полный объем диссертации составляет 142 страницы, включая 72 рисунка и 3 таблицы.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Водолазов, Николай Николаевич

Выводы. В третьей главе доказана теорема о том, что средняя величина динамического потока не может превышать величины стационарного потока. Однако из построенного примера 8 ясно, что динамический поток в определенные моменты времени может превосходить максимальную величину стационарного потока. В результате исследования динамического потока доказано существование потока с максимальным всплеском, предложен алгоритм нахождения максимального всплеска в сети.

Рассмотрены два варианта задачи о максимальном объеме в сети: вариант при котром поток, имеющий максимальный объем в сети в момент времени t, не продолжаем на все ^ е Z, и вариант, когда полученный поток должен быть продолжаем на все X е Z. Предложены алгоритмы для решения этой задачи. Доказано, что эти алгоритмы находят поток, имеющий максимальный объем.

ЗАКЛЮЧЕНИЕ

В настоящее время теория графов стала эффективным средством решения вопросов, относящихся к широкому кругу различных областей и имеющих важные практические приложения. В виде графов можно представить, например, схемы дорог и электрических цепей, карты, схемы управления и блок-схемы программ и т.п. Использование ЭВМ при решении прикладных задач с применением теории графов потребовало создания эффективных алгоритмов решения оптимизационных задач на графах.

Целью данной работы является поиск алгоритмов для решения задачи о максимальном потоке на графах с дополнительными ограничениями на достижимость, а также построение алгоритмов для поиска максимального всплеска в сети и нахождения максимального объема сети.

Для достижения поставленной цели были решены следующие задачи:

1. Доказана МР-полнота задачи нахождения максимального потока для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к > 2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимость.

2. Построены полиномиальные алгоритмы нахождения максимального потока для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к — 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями.

3. Исследована задача нахождения максимального всплеска в сети и приведен алгоритм ее решения.

4. Исследована задача нахождения максимального объема сети и приведен алгоритм ее решения.

В процессе исследования автором было расширено определение потока. В отличие от классического случая, где важно только число частиц, приходящих в вершину, в случае нестандартной достижимости эти частицы могут быть разного вида в зависимости от пройденного ими ранее пути. Поэтому поток определяется как множество пар, где каждая пара — путь из источника в сток и величина потока по этому пути.

В диссертационной работе подробно рассмотрен поток в сетях с барьерными ограничениями на достижимость, и проанализирован существовавший ранее алгоритм. Показано, что на некоторых графах (даже без барьерных ограничений) алгоритм «прорыва» [14] может не находить максимального потока. Автором работы построен алгоритм на основе алгоритма Эдмондса-Карпа, который обходит ограничения существовавшего ранее решения (алгоритм 2). Однако построенный пример показывает, что и этот алгоритм не всегда может найти максимальный поток.

Проанализированы причины, по которым алгоритмы, основанные на поиске увеличивающих цепей (такие как алгоритмы Форда-Фалкерсона и Эдмондса-Карпа), могут не находить решения. Рассмотрено обобщение задачи — поток на вспомогательном графе, построенном по исходному графу, в котором все пути разрешены, но некоторые дуги являются связанными. Потребовалось изменить определение величины разреза на таком графе.

Согласно работе [14] часть теоремы Форда-Фалкерсона о том, что максимальный поток ограничен сверху величиной минимального разреза, выполнена и для нового определения разреза. Однако на приведенных в данной работе примерах показано, что другая часть - о том, что существует поток, величина которого достигает величины минимального разреза, не выполнена. На основании этого делается вывод о неприменимости алгоритмов поиска максимального потока, основанных на поиске увеличивающих путей, в сетях с дополнительными ограничениями на достижимость.

В результате исследований автором построен новый алгоритм поиска максимального потока для графов со связанными дугами; рассмотрены случаи, при которых можно применять этот алгоритм.

Автором показано, что задача поиска потока на графах с дополнительными ограничениями на достижимость может быть ЫР-полна для некоторых видов достижимости. Для доказательства этого утверждения построен специальный вид достижимости — ЫР-достижимость.

Решение задачи 3-8АТ сведено к нахождению максимального потока в специально построенном графе с МР-достижимостью. Доказано, что решение задачи о максимальном потоке на графе, построенном в теореме об ИР-полноте, с ИР-достижимостью, эквивалентно задачам на том же графе для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к > 2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимость.

Для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к = 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями построены полиномиальные алгоритмы нахождения максимального потока.

На основе изучения динамического потока на графе и ограничений на величину максимального динамического потока было введено понятие средней величины потока и доказана теорема о том, что средняя величина потока не может превышать величины максимального стационарного потока. Приведен пример (пример 8), который показывает, что величина динамического потока может в некоторые моменты времени превосходить величину максимального стационарного потока.

В процессе анализа того, насколько динамический поток может превышать среднюю величину потока, введены определения максимального всплеска и максимального объема. В третьей главе были решены следующие задачи:

• Нахождение максимального всплеска на графе — динамического потока, имеющего максимально возможную величину в какой-то момент времени, не заданный заранее.

• Нахождение динамического потока, имеющего максимальный объем, т.е. потока, для которого сумма значений по всем дугам максимальна для некоторого момента времени.

Построены алгоритмы решения указанных задач: для первой задачи — алгоритм Эдмондса-Карпа с обратным поиском; для второй — алгоритм 4, доказаны теоремы о том, что эти алгоритмы находят правильное решение.

Для алгоритмов, разработанных в диссертационной работе, автором написана реализующая их программа «Моделирование потоков с ограничениями на достижимость» (прилагается на компакт-диске). Программа позволяет визуализировать представленные алгоритмы и выполнять их по шагам. В процессе работы алгоритмов можно наблюдать за конвертацией графа, изменением меток вершин и дуг графа и основными переменными алгоритма.

Цели и задачи, поставленные в диссертационном исследовании, были полностью решены: доказана ТМР-полнота задачи поиска макимального потока для некоторых видов ограничений на достижимость, для других видов достижимости построены полиномиальные алгоритмы поиска потока, построены и обоснованы алгоритмы поиска максимального всплеска и максимального объема сети, разработана программа, реализующая построенные алгоритмы.

Список литературы диссертационного исследования кандидат физико-математических наук Водолазов, Николай Николаевич, 2010 год

1. Ахо А. Построение и анализ вычислительных алгоритмов. / А. Ахо, Дж. Хопкрофт, Дж. Ульман. -М.: Мир, 1979. 536с.

2. Басакер Р. Конечные графы и сети. / Р. Басакер, Т. Саати; пер. с англ. -М.:Наука, 1973.-368с.

3. Басангова Е.О. Алгоритм нахождения максимального потока в частично-ориентированной сети. / Е.О. Басангова, Я.М. Ерусалимский // Дискретные структуры и их приложения. -Элиста: КГУ, 1988. С.23-28.

4. Басангова Е.О. Различные виды смешанной достижимости. / Е.О. Басангова, Я.М. Ерусалимский // Алгебра и дискретная математика: сб. — Элиста: КГУ, 1985. С.70-75.

5. Басангова Е.О. Смешанная достижимость на частично-ориентированных графах. / Е.О. Басангова, Я.М. Ерусалимский // Вычислительные системы и алгоритмы: сб. -Ростов-на-Дону: РГУ, 1983. С.135-140.

6. Басангова Е. О. Смешанная достижимость на частично-ориентированных графах. / Е.О. Басангова, Я.М. Ерусалимский. Деп. в ВИНИТИ. —1982. №5892-82.

7. Водолазов H.H. Поток на графах с ограничениями на достижимость: тр. науч. школы И.Б. Симоненко. / Водолазов H.H., Ерусалимский Я.М. -Ростов-на-Дону: Изд-во ЮФУ, 2010. С. 44-57.

8. Водолазов H.H. Максимальный всплеск в сети и максимальный объем сети. / Водолазов H.H., Ерусалимский Я.М. // Изв. вузов. Сев.-Кавк. регион. Естественные науки. 2010. - №6. — С. 9-13.

9. М.Диниц Е.А. Метод поразрядного сокращения невязок и транспортные задачи. / Е.А. Диниц // Исследования по дискретной математике. — М.:Наука, -1973.

10. Ерусалимский Я.М. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях. / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев-Кавк. регион. Естественные науки. -2003. -№2. С. 3-5.

11. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. 4-е издание. / Я.М. Ерусалимский -М.:Вузовская книга, 2001. 280с.

12. Ерусалимский Я.М. Достижимость на графах с условиями затухания и усиления. / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев.-Кавк. регион. Естественные науки. -2004. Спецвып. Математика и механика. -С. 110-112.

13. Ерусалимский Я.М. Многопродуктовые потоки в сетях с нестандартной достижимостью. / Я.М. Ерусалимский, Петросян А.Г. // Изв. вузов. Сев.-Кавк. регион. Естественные науки. Прил. -2005. -№6. С. 8-16.

14. Ерусалимский Я.М. Некоторые задачи достижимости на графах с ограничениями. / Я.М. Ерусалимский, С.Ю. Логвинов // Изв. вузов. Сев.-Кавк. регион. Естественные науки. —1996. —№2. С. 14-17.

15. Ерусалимский Я.М. Потоки в сетях со связанными дугами. / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев.-Кавк. регион. Естественные науки. Прил. -2003. № 8. С. 9-12.

16. Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью. / Я.М. Ерусалимский // Модели, графы и алгебраические структуры: сб. -Элиста, 1989.-С. 45-48.

17. Зыков A.A. Основы теории графов. / A.A. Зыков -М.: Наука, 1987. -384с.

18. Кристофидес H. Теория графов. Алгоритмический подход. / Н. Кристофидес. -М.: Мир, 1978. -432с.

19. Кузьминова М.В. Динамические периодические графы. / М.В. Кузьминова // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения XVIII». — Воронеж, 2007. С.97-98.

20. Кузьминова М.В. Ограниченные магнитные достижимости на ориентированных графах. / М.В. Кузьминова // Изв. вузов. Сев.-Кавк. регион. Естественные науки. Прил. -2006. -№6. С. 12-26.

21. Ope О. Теория графов. -2-е изд. / О. Ope -M.: Наука, 1980. 336с.

22. ЪА. Петросян А.Г. Многопродуктовые потоки в сетях с ограничениями на достижимость. / А.Г. Петросян // Математические методы в современных и классических моделях экономики и естествознания: сб. -Ростов-на-Дону, 2005.-С. 136-138.

23. Петросян А.Г. Потоки в сетях с биполярной достижимостью. / А.Г. Петросян // Изв. вузов. Сев.-Кавк. регион. Естественные науки. Прил. — 2006.-№3.-С.32-37.

24. Петросян А.Г. Потоковая задача в многопродуктовых сетях с нестандартной достижимостью. / А.Г. Петросян // Современныепроблемы математического моделирования: сб. -Ростов-на-Дону, 2005. — С.334-340.

25. Рихтер Дж. Программирование на платформе Microsoft .NET Framework /Дж. Рихтер; пер. с англ. — 2-е изд. М.: Издательско-торговый дом «Русская Редакция», 2003. — 512с.

26. Свами М. Графы, сети и алгоритмы. / М. Свами, К. Тхуласираман; пер. с англ. М.: Мир, 1984. - 455с.

27. Скороходов В.А Устойчивость и стационарное распределение на графах с нестандартной достижимостью./ В.А Скороходов // Изв. вузов. Сев.-Кавк. регион. Естественные науки. —2007. —№4. — С.17-21.

28. Скороходов В.А. Графы с магнитной достижимостью. Марковские процессы и потоки в сетях. / В.А. Скороходов. Деп. в ВИНИТИ. -2003. №410-В2003.

29. Скороходов В.А. Случайные блуждания и потоки в сетях с магнитной достижимостью. / В.А. Скороходов // Модели и дискретные структуры: сб. -Элиста, 2002. -С.93-100.

30. Форд JJ. Р. Потоки в сетях. / JI. Р. Форд, Д.Р. Фалкерсон; пер. с англ. -М.:Мир, 1966.-276с.

31. Харари Ф. Теория графов. / Ф. Харари. -М.: Мир, 1973. 300с.

32. Ahuja R. К. A fast and simple algorithm for the maximum flow problem. / R.K. Ahuja, J.B. Orlin. // Oper. Res. -1989. -No.37. PP. 748-759.

33. Ahuja R. K. Improved time bounds for the maximum flow problem. / R.K. Ahuja, J.B. Orlin, R.E. Tarjan. // SIAM J. Copmut. -1989. -No.18. PP. 939954.

34. Alon N. Generating pseudo-random permutations and maximum flow algorithms. / N. Alon // Inf. Proc. Lett. -1990. -No.35. PP. 201-204.

35. Aronson J.E. A survey of dynamic network flows. / J.E. Aronson // Annals of Operations Research. -No. 20. -1989. PP. 1-66.

36. Cook S.A. The complexity of theorem-proving procedures. / S.A. Cook. // Proceedings of the third annual ACM symposium on Theory of computing. ACM New York, NY, USA. 1971. -PP. 151-158.

37. Dantzig G.B. Application of the simplex method to a transportation problem. / G.B. Dantzig // In Activity Analysis and Production and Allocation. -New York: Wiley, 1951. -PP. 359-373.

38. Dinic E.A. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. / E.A. Dinic // Sov. Math. Dokl. -1970. -Noll.-PP. 1277-1280.

39. Edmonds J. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. / J. Edmonds, R.M. Karp //Journal of the Association for Computing Machinery. Vol. 19. - No. 2, -1972. - PP. 248-264.

40. Even S. On the complexity of timetable and multicommodity flow problems. / S. Even, A. Itai, A. Shamir. // SIAM J. Comput. -Vol. 5. -No. 4. -1976. -PP.691—703.

41. Ford Jr. L.R. Maximal flow through a network. / L.R. Ford Jr., D.R. Fulkerson. // Canad. J. Math. -1956. -No. 8. PP. 399-404.

42. Ford L.R. Constructing maximal dynamic flows from static flows. / L.R. Ford, D.R. Fulkerson // Operations Research. -1958 -Vol.6 PP. 419-433.

43. Gabow H.N. Scaling algorithms for network problems. / H.N. Gabow // J. Comput. Syst. Sei. -1985. -No.31. PP. 148-168.

44. Galiil Z. An 0(EV log" V) algorithm for the maximal flow problem. / Z. Galiil, A. Naamad. // J. Comput. Syst. Sei. -1980. -No.21. PP. 203-217.5 2

45. Galil Z. An 0(V3E2) algorithm for the maximal flow problem. / Z. Galil // Acta Inf. -1980. -No. 14. PP. 221-242.

46. Goldberg A. V. A new approach to the maximum-flow problem. / A.V. Goldberg, R.E. Tarjan. // J. ACM. -1988. -Vol.35. -No.4. PP. 921-940.

47. Goldberg A. V. A New Approach to the Maximum-Flow Problem. / A.V. Goldberg, R.E. Tarjan // Journal of the Association for Computing Machinery. -Vol.35. -No. 4.-1988. PP. 921-940.

48. Graves S.C. A Minimum Concave-Cost Dynamic Network Flow Problem with an Application to Lot-Sizing. / S.C. Graves, J. B. Orlin // Networks -Vol.15.1985-PP. 59-71.

49. Helmberg C. Network Models with Convex Cost Structure like Bundle Methods. / C. Helmberg // Models and Algorithms for Optimization in Logistics, Dagstuhl Seminar Proceedings. http://drops.dagstuhl.de/opus/volltexte/2009/2190

50. Karp R.M. Reducibility Among Combinatorial Problems. / Karp R.M. // Complexity of Computer Computations; R. E. Miller and J. W. Thatcher (editors). -New York: Plenum, 1972. PP. 85-103.

51. Karzanov, A. V. Determining the maximal flow in a network by the method of preflows. / A.V. Karzanov // Sov. Math. Dokl. -1974. -No. 15. PP. 434-474.

52. King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. // In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, Fla., Jan. 27-29). ACM, New York, 1992. -PP.157-164.

53. King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. // J. Algorithms. -1994. -No.17. PP. 447-474.

54. Lawler E.L. Combinatorial optimization: networks and matroids. / Lawler E.L. -New York: Holt, Rinehart and Winston, 1976. -374 p.

55. Malhorta V.M. An 0(\ V \3 ) algorithm for finding maximum flows in networks. / V.M. Malhorta, Pramodh Kumar M., S.N. Maheshwari // Inf. Process. Lett. -1978. -No.7. PP. 277-278.

56. Ning Xuanxi. The Blocking Flow Theory and its Application to Hamiltonian Graph Problems. / Ning Xuanxi, Ning Angelika. -Germany, Aachen: Shaker Verlag GmbH, 2006. 249p.

57. Orlin J.B. Maximum-throughput dynamic network flows. / J.B. Orlin // Math. Progr. -1983. -Vol.27. PP. 214-231.

58. Papadimitriou C.M. Computational complexity. / C.M. Papadimitriou. // Addison-Wesley, 1994, -523p.

59. Phillips S. Online load balancing and network flow. / S. Phillips, J. Westbrook. // In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, 1993. PP. 402-411.

60. Skutella M. An Introduction to Network Flows Over Time. / M. Skutella // Research Trends in Combinatorial Optimization. Berlin: Springer Berlin Heidelberg, -2009. PP. 451-482.

61. Sleator D.D. A data structure for dynamic trees. / D.D. Sleator, R.E. Tarjan. // J. Comput. Syst. Sei. -1983. -No.26. PP. 362-391.

62. Tarjan R.E. A simple version of Karzanov's blocking flow algorithm. / R.E. Tarjan // Oper. Res. Lett. -1984. -No.2. PP. 265-268.