• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Blocking Flows

    David Karger

    Last Time: Scaling

    Blocking Flows

    Extension of shortest augmenting path.
    Dinic’s algorithm:

    Blocking Flows in Unit-capacity Graphs

    Wait a minute: This does not sound too impressive. We already knew how to do that! (Our first algorithm run in time \(O(mnU)\).) Why bother?

    How to get a better bound for unit-capacities?

    Blocking Flows in General Graphs

    What breaks when we try the above analysis in general graphs?

    Scaling Blocking Flows

    Basic idea:

    End result: Implementation of the blocking flow primitive in only \(O(m\log n)\) (instead of \(O(mn)\)) time. (\(O(\log n)\) overhead comes from the splay trees.)

    \(\Rightarrow\) Gives an \(O(mn\log n)\) time algorithm!

    Beyond Flow Decomposition Barrier