# Combinatorial Optimization Lecture Notes by Goldberg A.V. By Goldberg A.V.

Similar combinatorics books

Handbook of Algebra Vol III

1998 . .. a very good index is incorporated with a view to aid a mathematician operating in a space except his personal to discover enough details at the subject in query.

Additional resources for Combinatorial Optimization Lecture Notes

Example text

If f (w x) > 0 then f (x w) < 0 = u(x w) which means that (x w) 2 Ef which in turn implies w 2 S . This is a contradiction and so f (w x) 0 8w 2 S c x 2 S . Let f (W X ) be the total ow from a subset of nodes W to a subset of nodes X so that f (S c S ) 0. So now 2 ef (S ) = f (V S ) = f (S S ) + f (S c S ) = f (S c S ) 0 . But ef (S ) > 0 so we obtain the required contradiction and the lemma is proved. Lemma 10. 8v d(v ) 2n ; 1. Proof. It su ces to examine active nodes because d(v) can only increase when v is active.

It follows that the second p part takes O( nm) time. The second phase of the bipartite matching algorithm is very simple and fast. First, all excesses at nodes y 2 Y are returned to nodes in X . To see that this is trivial, note that every node with excess in Y must have an outgoing residual arc to a node in X . Note now that all excesses are unit, since the residual indegree of any node in X is zero if it has a unit of excess. Now, to see that it is trivial to return all the excesses to the source from X , note that because the rst phase ends the rst time the minimum distance label of a node 4.

24. A blocking ow is not necessarily a maximum ow. Example 8. Note that a blocking ow is not necessarily a maximum ow. 24, the ow is a blocking ow but not a maximum ow. Definition 3. , for all (v w) 2 E , l(w) = l(v ) + 1. Definition 4. Given a network G = (V E ) and a ow f, de ne Gl (f ) = (V A) where A = f(u v ) 2 Ef jl(v ) = l(u) + 1g and l(v) is the breath rst search distance of v from the source s in the residual graph Gf . 25. The following lemma implies that the algorithm terminates in at most n ; 1 iterations.