Efficient Algorithms for Maximum Flow.

1. Show how you can implement each stage of the Edmonds-Karp algorithm
in O(nm) time. Hint: Do a BFS and divide vertices into layers. Consider only
edges directed from layer i to layer i+1. Show how it is possible to find
the next augmenting path in a stage in O(n) time. This gives an algorithm,
called Dinic's algorithm, with time complexity O(n^2m).

2. Dinic's algorithm can be further improved by augmenting along several
shortest augmenting paths at the same time. Again consider the layered
network obtained by dividing vertices into layers. For a vertex v,
let In(v) = sum of capacities of edges entering v,
and Out(v) = sum of capacities of edges leaving v. Let d = minimum of
In(v), Out(v) over all vertices v. Show how the flow can be augmented by
d units in O(n+k) time, where k is the number of edges that get deleted
from the residual network. Using this show how you can implement each stage 
of the Edmonds-Karp algorithm in O(n^2) time. This gives an overall 
algorithm with time complexity O(n^3). (This is known as the Maheshwari-
Pramodh Kumar- Malhotra, MPM algorithm).

3. Suppose all edges in the network have unit capacity.  Show how the
maximum flow can be found in O(m\sqrt(m)) time. Hint: Suppose the distance
between s and t in the residual network is d. How far can the flow be from
the maximum flow?

4. Suppose in the pre-flow push algorithm, we always choose a vertex
with excess flow that has maximum h value, for applying push or relabel
operations. Show that this gives an O(n^3) time algorithm for max flow.