Let G = (V, E) be a directed graph with integer edge capacities c : E Z0 . Suppose you have already computed a maximum flow f in G.

(a) Describe and analyze an algorithm to update the maximum flow after the capacity of a single edge is increased by 1.

(b) Describe and analyze an algorithm to update the maximum flow after the capacity of a single edge is decreased by 1. You algorithm for both parts should be faster than computing a new maximum flow from scratch.