=^_^= Кружок обучения мастерству программирования при СПбГУ

Лекции группы A0 - Семинар 01 - про Preflow Push

Семинар по потокам :
  1. Идея высотной функции в поиске потока (проталкивания предпотока)
    1. PreflowPush за O(V^2E) + док-во
    2. LiftToFront за O(V^3) + док-во
  2. Эвристики, улучшающее время и асимптотику:
    1. Max Height
    2. Дырки в высотной функции и что они значат
    3. Global Relabeling (h[v] =~ расстояние до стока в остаточной сети)
  3. Алгоритм Хао-Орлина, ищущий глобальный MinCut в графе за O(V^3)
Литература [Кормнен (rus) + Статьи (en) + Лекции Гольдберга (en)]
  1. В первую очередь рекомендуется:
    1. Лекции, которые читает Андрей Гольдберг (Goldberg "Combinatorial Optimization Lecture Notes")
  2. Часть первая
    1. "Cormen, Leiserson, Rivest, Stein. Introduction to algorithms (2ed, MIT, 2001)(C)(984s).djvu" (from page 571)
  3. Часть вторая
    1. http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm
    2. "Goldberg, Tarjan - A New Approach to the Maximal Flow Problem.pdf"
    3. "Two-Level Push-Relabel Algorithm for the Maximum Flow Problem.pdf"
  4. Часть третья
    1. "Hao, Orlin - A Faster Algorithm for Finding the Minimum Cut in a Graph.pdf"
    2. "A simple Min Cut algorithm.pdf"
Внимание: статьи не нужно искать! ссылки все здесь.