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