Problems
1. (20 pts) Exercise 26.1-3.
2. (20 pts) Exercise 26.1-4.
3. (20 pts) Exercise 26.2-2.
4. (20 pts) Exercise 26.2-10 (Extra Credit)
5. (30 pts) Implement Push-Relabel for nding maximum ow.
Extra Credit: use relabel-to-front idea from Chapter 26.5 with the Discharge procedure.
6. (15 pts) Explain in a brief paragraph the following sentence from textbook page 737: \To make the pre ow a legal ow, the algorithm then sends the excess collected in the reservoirs of over owing vertices back to the source by continuing to relabel vertices to above the xed height jV j of the source".
7. (20 pts Extra Credit) Exercise 26.4.4
1
