DOC PREVIEW
UT Dallas CS 6363 - notes-6363-001-2015s-28-p2

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

c� Balaji Raghavachari 200 Algorithm Design and Analysis✬✫✩✪Flow: examplesacdbt154101271053c� Balaji Raghavachari 201 Algorithm Design and Analysis✬✫✩✪Augmenting pathsacdbt154101271053• Residual capacity of an edge cf(u, v) = c(u, v) − f(u, v)(extra flow t hat could be sent through (u, v)).• Find augmenting path from s to t, a path in whichthe re sidual ca pacity of all edges are positive.• In the example, path s − c − d − a − b − t is anaugmenting path. Capacity of pat h is the minimumresidual capacity of it s edges (in example, it is 4).c� Balaji Raghavachari 202 Algorithm Design and Analysis✬✫✩✪Flow of 4 unitssacdbt154/104/124/71034/44/5c� Balaji Raghavachari 203 Algorithm Design and Analysis✬✫✩✪Another augmenting path of capacity 3sacdbt154/104/71034/44/54/12c� Balaji Raghavachari 204 Algorithm Design and Analysis✬✫✩✪Flow of 7 unitssacdbt3/157/107/124/73/104/44/53/3c� Balaji Raghavachari 205 Algorithm Design and Analysis✬✫✩✪Augmenting path of 3 unitssacdbt7/103/104/44/53/33/157/124/7c� Balaji Raghavachari 206 Algorithm Design and Analysis✬✫✩✪Flow of 10 unitssacdbt6/157/1010/127/73/104/44/53/3c� Balaji Raghavachari 207 Algorithm Design and Analysis✬✫✩✪A blocking flowsacdbt6/157/1010/127/73/104/44/53/3• Observe that any directed path from s to t has to gothrough a saturated edge (f (u, v) = c(u, v)).• Blocking flow: a flow in which any directed path froms t o t has a saturated edge.• A blocking flow may not be a maximum flow. Thereforethe gree dy algorithm fails to find a maximum flow.c� Balaji Raghavachari 208 Algorithm Design and Analysis✬✫✩✪Augmenting path that pushes flow against direction of edge• It is possible to augment flow by pushing flow back onsome edge. For example, consider the path s − a − d − t:sacdbt7/1010/127/74/43/36/154/53/10• We can “send flow” from a to d by reducing the flowfrom d to a (up to 4 units, t he flow from d to a).• Residual capacity cf(a, d) = f(d, a) = 4.c� Balaji Raghavachari 209 Algorithm Design and Analysis✬✫✩✪Flow of 14 unitssacdbt7/1010/127/77/104/40/53/310/15Is this a maximum flow?c� Balaji Raghavachari 210 Algorithm Design and Analysis✬✫✩✪Proof of maximum flowsacdbt7/1010/127/77/104/40/53/3ST10/15• Consider cut S = {s, a, b} and T = {c, d, t}.• All edges from S to T are saturated.• All edges from T to S have no flow.• Therefore flow is a maximum flow (of 14 units).c� Balaji Raghavachari 211 Algorithm Design and Analysis✬✫✩✪Ford-Fulkerson’s algorithm1. Start with an empty flow f : f (u, v) = 0 for (u, v) ∈ E.2. Construct residual network Gf:• For each edge (u, v) ∈ E, add edge (u, v) to Gfwithresidual capacity cf(u, v) = c(u, v) − f(u, v).• Add reverse edge (v, u) with cf(v, u) = f(u, v) .• Aggregate capacities of multiple edges in samedirection. Drop edges with zero residual capacity.3. If there is no path in Gffrom s to t, stop.4. Otherwise, find a path P from s to t, and augment flowalong P : for all edges (u, v) ∈ P , set f (u, v) = f (u, v) + por f (v, u) = f (v, u) − p, where p = mine∈P{cf(e)}.[Edmonds-Karp algorithm: use BFS to find path in Gffrom s to t.] Repeat steps 2-4 until done.c� Balaji Raghavachari 212 Algorithm Design and Analysis✬✫✩✪Residual network, Gf, of flow in Slide 206sacdbt6/157/1010/127/73/104/44/53/3sacdbt43496310277731Augmenting path s − a − d − t is a path from s to t in Gf.c� Balaji Raghavachari 213 Algorithm Design and Analysis✬✫✩✪Illustration of Edmonds-Karp algorithmsacdbt154101271053sacdbt154101271053c� Balaji Raghavachari 214 Algorithm Design and Analysis✬✫✩✪sacdbt4107/127/710537/15sacdbt841057105377sacdbt4/44/107/127/74/10537/15c� Balaji Raghavachari 215 Algorithm Design and


View Full Document

UT Dallas CS 6363 - notes-6363-001-2015s-28-p2

Documents in this Course
Exam #1

Exam #1

5 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

greedy

greedy

4 pages

siphon

siphon

18 pages

hwk5

hwk5

3 pages

Load more
Download notes-6363-001-2015s-28-p2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view notes-6363-001-2015s-28-p2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view notes-6363-001-2015s-28-p2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?