This counterexample (from Chvatal [1983]) illustrates how the version of the FordFulkerson method where augmenting paths need not have as few arcs as possible may not terminate for a problem with irrational arc flow bounds. Consider the max-flow problem shown in Fig. 3.12. (a) Verify that an infinite sequence of augmenting paths is characterized by the table of Fig. 3.12; each augmentation increases the divergence out of the source s but the sequence of divergences converges to a value, which can be arbitrarily smaller than the maximum flow. (b) Solve the problem with the Ford-Fulkerson method (where the augmenting paths involve a minimum number of arcs, as given in Section 3.2)
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here