We can speed up the Edmonds-Karp fattest path algorithm, at least for networks with small integer...

 

Transcribed Image Text:

We can speed up the Edmonds-Karp "fattest path" algorithm, at least for networks with small integer capacities, by relaxing our requirements for the next augmenting path. Instead of finding the augmenting path with maximum bottleneck capacity, we find a path whose bottleneck capacity is at least half of maximum, using the following capacity scaling algorithm. (This algorithm was actually proposed by Edmonds and Karp.) Assume all the edge capacities are positive integers less than U = 2k for some integer k. The scaling algorithm maintains a bottleneck threshold A; initially, we set A U. In each phase, the algorithm augments along paths from s to t in which every edge has residual capacity at least A. When there is no such path, the phase ends, we set A [A/2], and the next phase begins. The algorithm ends when A = 0. (a) How many phases will this algorithm execute in the worst case? (b) Let f be the flow at the end of a phase for a particular value of A. Prove that the capacity of a minimum cut in the residual graph G is at most . (c) Prove that in each phase of the scaling algorithm, there are at most 2E augmentations. (d) What is the overall running time of the capacity scaling algorithm? We can speed up the Edmonds-Karp "fattest path" algorithm, at least for networks with small integer capacities, by relaxing our requirements for the next augmenting path. Instead of finding the augmenting path with maximum bottleneck capacity, we find a path whose bottleneck capacity is at least half of maximum, using the following capacity scaling algorithm. (This algorithm was actually proposed by Edmonds and Karp.) Assume all the edge capacities are positive integers less than U = 2k for some integer k. The scaling algorithm maintains a bottleneck threshold A; initially, we set A U. In each phase, the algorithm augments along paths from s to t in which every edge has residual capacity at least A. When there is no such path, the phase ends, we set A [A/2], and the next phase begins. The algorithm ends when A = 0. (a) How many phases will this algorithm execute in the worst case? (b) Let f be the flow at the end of a phase for a particular value of A. Prove that the capacity of a minimum cut in the residual graph G is at most . (c) Prove that in each phase of the scaling algorithm, there are at most 2E augmentations. (d) What is the overall running time of the capacity scaling algorithm?