Uncertainty Whiteboard Seminar

Computing Maximum Flow with Augmenting Electrical Flows

I will explain how to compute the maximum flow in a graph by iteratively routing electrical flows in the residual graph. The resulting algorithm provides the state of the art running time bounds for the unit capacity maximum flow problem.

No special background will be assumed.