### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 707 Class Note for CSE 565 at PSU

### View Full Document

## 26

## 0

## Popular in Course

## Popular in Department

This 6 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 26 views.

## Similar to Course at Penn State

## Reviews for 707 Class Note for CSE 565 at PSU

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Algorithm Design and Analysis LECTURES 25 26 Network Flow 0 Maximum FOW 0 Minimum Cut 0 FordFulkerson Sofya Raskhodnikova 10242007 S Raskhodnikova based on slides by E Demaine C Leiserson K Wayne Soviet Rail Network 1955 Reference 0n the history of the transportation and maxmum fow probems Alexander Schrijver in Math Programming 91 3 2002 Maximum Flow and Minimum Cut Max flow and min cut Two very rich algorithmic problems Cornerstone problems in combinatorial optimization Beautiful mathematical duality Nontrivial applications reductions Data mining V Network reliability Openpit mining V Distributed computing Project Selection V Egalitarian stable matching Airline Scheduling V Security of statistical data Bipartite matching V Network intrusion detection BaSeball elimination V Multicamera Scene reconstruction Image segmentation V Many many more Network connectivity Minimum Cut Problem Flow network Abstraction for material flowing through the edges 6 V E directed graph no parallel edges Two distinguished nodes 3 source t Sink Ce capacity of edge e source 5 k 8 gt 6 10 sink 4 6 15 10 15 capaCIty 39 4 30 r 7 Cuts Def An st cut is a partition A B of V with s e A and t e B Def The capacity of a cut A B is capA B Z Ce e out ofA s e lo lt9 4 6 15 10 Capacity 10 5 15 4 30 Q 30 Cuts Def An st cut is a partition A B of V with s e A and t e B Def The capacity of a cut A B is capA B Z Ce 2 out ofA H O 10 10 15 Capacity 9 15 8 30 4 39 62 M mun Cu hdzlun MM 54 cm promem Fmd an 54 cm of mmmum capacwy Hm Def An 39 W I s a funcnon f from E m rem number39s vhav sans es For each 2 s E o s m s cm capacwy For each y b v 7 s v eonseryanon Ef quot Def W12 uh ofa owfws VKf mev Icnd n Fluv sz An 39 39I v s a mcnon f from E to ma numbers that sans zs Fov each 2 e E 0 5 f9 3 4 capacny For each y s v 45 v Em conseryanon i1 v c9 4 u u a D x 2 WW a u e n 1 u n Haw a n U G 30 0 Indyn Fluquotth Max ow prob zm Fmd 4 ow of maxmmv va uz m n A m 4 15 n n m z x e G s g e 3 m e m malty a 15 quot A 395 Iquot my an H m a w a quot Hun Cm Fbw vu ue emma Lev f be any ow and M A a be my 54 cm Then We nev ow mm across Me an s eun vo vhe amoum eavmgs 2f Eff f mu um unn an 9 i v m y u J n u n m 4 x v s Q g 1 Q a m clpxwy u quot u H quot aw an M w CB 3 27 Hun udle ow vu ue emma Lev f be my ow md In A a be my 54 cm Then We nev ow 52m across Me cm s equd vo vhe amoum mmg 5 2f 2m va Aau A me n o I y E H n m 3 u g u quot n andha an h Flow Can new yame Lemma Lev f be my ow and 2 A a be my 54 cm Then vhe nev ow 52m across Me an rs equm vo vhe amoum mymgs 2m A 20 yf quotMA mu L 39 D m n A n A 4 5 l n n z 5 s I L m 1 ln a n n quot H guruIqu In Flalandch ow yame Lemma Lev f be my by md 12 A a be my 34 cm Then 2 NF 2 fm Kflv u mm Proof 0 2 t an quotunmmmmms z 2 2fe 2 my mm A mu m 2 f 2 fev I A A Flun and Cuquot Wzak duamy Lev f be my ow and 2 A a be my s4 cm Then we yam of me ow 3 m mosv H12 capacny of H12 cm amp9pm a Flumm th MCIquot Weakduamy Lev f be my ow Then y g capA s for my sir cm A 5 Pf f Efkk 2 m MA WA 2 N A S 24 GA lt MIA E v 9 m n n I lt5 x 3 m g n u A 395 lquot B In D m l Cardigan of anll39y Coro kry Lev f be my ow md m A Bb2 my 54 cm If ym capA a wen i S omax by and A B S 0 mm 54 cm VduoIha mm 39 a Humta An I 4 n y 9 3 3 m a n a u an You39d I H Flu Algalmu Grudy abombm Stav with my o m an edge e e e Fund msrv pm 9 were each edge has e e 52 Aughem How atmgpmb v Rweav unntyou 92v stuck n D an m an U m 20 n Modal0 TM a It Flu AlgalMm Grudy a go 39hm 5m mm m 2 o for on m9 2 a e Fund av 54 pm p where each edgz has 2 lt cm Augva ow along pmh v Repzav unnl you 9239 stuck 2n 1 n zn 10gt TM a In How AlgorMm Srnay dgo vhm svav mm m 2 o for on M9 2 e PM 01454 pom p mm each edge has 2 lt cm Augva ow alongpmh v Repzm unnlyou 92v mu Mummm pgmmuum m a m I IIID Um I I I I H N V 30 may gun m as n 1 2n Mun m ncIiMISrqh Orwgma edge 2 W E E m How my mummy cm 0 7 O n 39b stwdual 2ng Wo How am 2uva vd2 vu I Resmmcmny t quotj Ac vfe M 1 E 0 me M K h E uuquot Resmasgwh 5 VE Resmm edges wuh posmve res dual cagomy Ey2f2ltc2 u 239c2gt0 FwFukum Mme FwdPutnam mam nuw f i c w 6 0 0 v 10 20 so ndsU mo 0 qukum mom 0 4 aw many E 0 x E 0 IO 2 0 B 60 10 o o E a no 9 10 Hdll U JF 4 39 mmml twenty 6 IO 2 a 6 10 a 10 4 9N3 10 gt9 6 FwdFukm MystOhm 6 10 10 so 0 2 a 10 2 0 ya 2 103 4 ML 9 0 QI 4 5 a 2 2 8 6 10 lo g 9 2 8 mm o Frd Fukcnn MystOhm o 4 5 10 E 9 o 0 2 2 9 6 ya 0 6 6 gt2 E 10 10 1 9 10 n d In 4 6 10 2 a 6 10 FNFularun ume FwFukum Alyfi ml FMFuImm algaInn FMFuksm algaInn nadirII Hundull 3 1 6 g 2 7 6 1 10 jL 9gt4H Anyum rah Algal A Nauru w 1 mg u for Gd quotsue mqg q q MC 1 Ann mquot macawum nannu laquot int i in t Ila u I Mn I m Augmemng pm Vhiorzm How i s umax ow m Men are no augmemmg poms Ma be mtwcuv vheorem Hmrhmswrnrshmnm 196e FadrFulersm 19517 The value of Vlw max ow lt3 equalvo the va1u2 of Me mm 34 cu w W2 prove mm stmuhaniousw by snowmg 0quot 41002 eqmvahzm I Thzrt mm mm cm A mm mm ic A s u rm f r max ow and we I nunsI cu m rum 1 no agmzmng path mum to f a H ms was me coro ary m weak duamy mm H m Weshowcmtraposwwe Ln v be aim If there mm m nugmkmmg per thn W cm uner v by min flow along paquot has of MalFlu Minaquot Thorun w 0 Lev r be afbw mm m auguemng yams Ln A be m oivirvcls rmnhnbll from s n rudunl gain 8 defnmmofA 6 A By defmmon u A VUI INF XIII 11 A a 261 0 emu vr lgnd nakm Running Tim Assumpnon AH cwacmes are mvegers bevweenl m c Invarvmv Every new value m andevew 7392er cmcrvy g e remams an 2ng vhrougwm vhe uhgomhm Theorem The abgomhm Vzmmmes m an mosv mg nC nemnms w Etch augmemmm moreasz value by av seam Runmng Mme of FordrFu1k2rsonOmnC Space mm Comm If c 1Ford Fullt2Mon runs n omquot m2 Imegrchvy Morequot 1v 0 cwacmes m mvegm mm thrc busts a max ow f m mm every ow mm 2 s an mveger Pi Smcz algagtth ummvzs thorim follows mm mme A

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.