Let G = (V, E) be a flow network with source s, sink t, and integer capacities.

Question:

Let G = (V, E) be a flow network with source s, sink t, and integer capacities. Suppose that we are given a maximum flow in G.
a. Suppose that the capacity of a single edge (u, v) ⁪¬ E is increased by 1. Give an O (V + E)-time algorithm to update the maximum flow.
b. Suppose that the capacity of a single edge (u, v) ¬⁪ E is decreased by 1. Give an O (V + E)-time algorithm to update the maximum flow.