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