Capacity Scaling | Network Flow | Graph Theory

Explanation video of the capacity scaling heuristic on flow networks
Next video: • Capacity Scaling | Net...
Ford Fulkerson explanation video:
• Max Flow Ford Fulkerso...
Ford Fulkerson source code video:
• Max Flow Ford Fulkerso...
Algorithms repository:
github.com/wil...
Video slides:
github.com/wil...
Personal website:
www.williamfise...
===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on TH-cam:
www.udemy.com/...

[@phillipyang5899]

10 mins here >> 3 hr lecture from a university professor. Great work and thank you

[@zucchinirosti]

5 min at times 2 speed

[@theexplorer9012]

1 min at 10 x

[@yoonchaena671]

Thank you~! your good explanations with good examples are really helpful~!

[@jarno9340]

Thank you! I suppose cannot be explained better!

[@pietropecora1335]

The intro music made me feel like I was in a WiiSports

[@pietropecora1335]

but great vid!

[@siddhantwadaskar6914]

Thank you so much! This video is super concise and it is nicely explained!

[@gillfin4188]

The video is way underrated

[@ederismaelalanisfernandez3664]

Thank you so much!

[@ShantanuGodbole-fg7eu]

makes it look so simple

[@LifeIn_Japan]

Thank you

[@larubiano0]

Thanks, saved me

[@pranshugoyal6471]

shouldn't we select our first delta value based on only edges that go out of S and not the whole graph as you told? If the edge between 2 and T has a capacity of 16, then delta would be 16 and hence there is no edge coming out of S that has remaining capacity greater than equal to 16

[@WilliamFiset-videos]

Yup, I think that would also work!

[@ayushjain4122]

How do u remember these algorithms and keep in mind..
I always implement them but keep forgetting them and when i go back i just can't remember basic algos also.
I am currently junior undergraduate student and find it very difficult.
Please help me out.

[@ayushjain4122]

hytwoxy Persistence is the key.☺️

[@ranjithkamalakannan6420]

If there are two edges with capacity >= delta, do we take the bigger one?

[@abdulkhan6886]

i love u

[@PB-mj9fm]

Hi William.
This is truly an awesome series which I'm super thankful for!
A question: In this video at around (th-cam.com/video/1ewLrXUz4kk/w-d-xo.html) you and the slide says that we continue while Delta > 0, but as we continue to divide Delta by 2 the value would never become 0 or less.
Was the intention to say less than 1 or am I missing something?

[@cryonim]

technically it means flooring(delta/2) because it will be an integer and fractional integer values round up.

[@codelyo_ko9123]

1/2 = 0 in euclidean division

[@erinbristow9592]

Yes, the variation that my prof taught was >= 1

[@erinbristow9592]

But also, an inherent assumption for Ford-Fulkerson is that all capacities MUST be integers.

[@xhamadeex]

I love you woman