City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Selected Topics in Network Flows
Saint Petersburg / spring 2017, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

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

  1. Задача о максимальном потоке и простейшие способы ее решения: алгоритмы Форда-Фалксерсона, Эдмондса-Карпа и Диница

  2. Оценки Карзанова для количества фаз алгоритма Диница

  3. Масштабирование пропускных способностей

  4. Проталкивание предпотока: общая схема, разгрузка вершин

  5. Стратегии разгрузки предпотока

  6. Быстрая декомпозиция мультитерминальных потоков

  7. Двухфазные алгоритмы проталкивания предпотока

  8. Эвристики, ускоряющие работу алгоритмов проталкивания предпотока

  9. Параметрический максимальный поток

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

  11. Динамические деревья в задачах о максимальном потоке

  12. Алгоритм Гольдберга-Рао

  13. Свободные мультипотоки: теорема Ловаса-Черкасского, алгоритм Ибараки-Карзанова-Нагамочи

  14. Бипотоки и биразрезы в неориентированных графах: теорема Ротшильда-Винстона, алгоритм Ху

  15. Потоки в кососимметрических и двунаправленых графах, приложения к недвудольным паросочетаниям

Date and time Class|Name Venue|short Materials
13 May
17:20–18:50
Лекция 1, Lecture ПОМИ РАН video
13 May
19:10–20:40
Лекция 2, Lecture ПОМИ РАН video
14 May
11:15–12:45
Лекция 3, Lecture ПОМИ РАН video
14 May
13:00–14:30
Лекция 4, Lecture ПОМИ РАН video
14 May
15:30–17:00
Лекция 5, Lecture ПОМИ РАН video
20 May
17:20–18:50
Лекция 6, Lecture ПОМИ РАН video
20 May
19:10–20:40
Лекция 7, Lecture ПОМИ РАН video
21 May
11:15–12:45
Лекция 8, Lecture ПОМИ РАН video
21 May
13:00–14:30
Лекция 9, Lecture ПОМИ РАН video
21 May
15:30–17:00
Лекция 10, Lecture ПОМИ РАН video