Advanced Data Structures

Fall 2003

[ CIS 410/510 | CIS | UO | News ]

Assignment 7

Due Wednesday Nov. 26

  1. Modify the setting of Prim-Dijkstra algorithm to arrive at the solution of the maximum bottleneck problem (page 91.) Give the resulting implementation of the maximum capacity augmentation algorithm for the max-flow problem.

  2. Solve he max-flow problem for the network in Figure 8.4 using the three algorithms discussed in class. For each algorithm, show the results of each augmentation step.
    1. the maximum capacity augmentation algorithm;
    2. the shortest path augmentation algorithm of Edmonds-Karp;
    3. the advance-augment-retreat algorith by Dinic.