\documentclass{article} \usepackage{me} \setlength{\parindent}{0pt}
\begin{center} Lecture 10: Blocking Flows \end{center}

Last Time

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

Dynamic Trees/Link-Cut Trees

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