CS 577: Introduction to Algorithms Homework 8
Out: 11/15/18 Due: 11/20/18
Ground Rules
The homework is worth 5 points (out of a total of 100 points you can accumulate in this course).
The homework is to be done and submitted individually. You may discuss homework problems with at most one other person from either section (and mention this person’s name on your submission), but you must write up solutions on your own.
You are not allowed to consult any material outside of assigned textbooks and material the instructors post on the course websites. In particular, consulting the internet will be considered plagiarism and penalized appropriately.
The homework is due at 11:59 PM on the due date. No extensions to the due date will be given under any circumstances.
Homework must be submitted electronically on canvas. We will not accept paper submissions. Canvas accepts files in pdf/doc/jpeg formats.
Problem (page limit: 2 pages)
For the network G above determine the max s-t flow, f ∗, the residual network Gf ∗ , and a minimum s-t cut.
An edge in a flow network is called upper-binding if increasing its capacity by one unit increases the maximum flow in the network. Similarly, an edge in a flow network is called lower-binding if reducing its capacity by one unit decreases the maximum flow in the network. Identify all of the upper-binding and all of the lower-binding edges in the above flow network.
Describe and analyze an algorithm for finding all of the upper-binding edges in a flow network G when given a maximum flow f ∗ in G. Your algorithm should run in time O(n + m), where n is the number of nodes and m is the number of edges.
