Избранные главы теории потоков

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

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

От слушателей предполагается знакомство с базовыми понятиями алгоритмической теории графов.

Предполагаемые темы, которые будут затронуты на занятиях:

— Задача о максимальном потоке и простейшие способы ее решения: алгоритмы Форда-Фалксерсона, Эдмондса-Карпа и Диница
— Оценки Карзанова для количества фаз алгоритма Диница
— Масштабирование пропускных способностей
— Проталкивание предпотока: общая схема, разгрузка вершин
— Стратегии разгрузки предпотока
— Быстрая декомпозиция мультитерминальных потоков
— Двухфазные алгоритмы проталкивания предпотока
— Эвристики, ускоряющие работу алгоритмов проталкивания предпотока
— Параметрический максимальный поток
— Задача о подграфе максимальной плотности
— Динамические деревья в задачах о максимальном потоке
— Алгоритм Гольдберга-Рао
— Свободные мультипотоки: теорема Ловаса-Черкасского, алгоритм Ибараки-Карзанова-Нагамочи
— Бипотоки и биразрезы в неориентированных графах: теорема Ротшильда-Винстона, алгоритм Ху
— Потоки в кососимметрических и двунаправленых графах, приложения к недвудольным паросочетаниям