Unweighted Bipartite Matching | Network Flow | Graph Theory

What is and how to solve the unweighted bipartite graph matching problem

Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on YouTube:

Algorithms repository:

Video slides:

Personal website:

[ShortGiant]

Woah. My brain just expanded a little.

[FallenAngels-mu]

"Thank you so much for watching this video". No, THANK YOU for making these wonderful tutorials, amazed by this one.

[babakmahmoudian]

Thank you! This is extremely helpful. I was going to spend the next couple of days learning about Max flow and Bipartite matching; never could've imagined learning so much in less than an hour!

[olae]

I'm having a course of Algorithms and Datastructures atm, and your videos are extremely helpful, thank you so much!

[sabeernarula]

This is the best video on the internet

[orbuluh_jp_notes]

Thanks so much for all the series ... it's amazing. And how you link every piece together is really clear.

[madhukiranattivilli]

Hey William Fiset :

@4:05 -- "weighted, directed, non-bipartite graph" -- min cost perfect match

I've implemented the dynamic programming solution for this

Felt nice :)

I'd to implement this as part of solving the Christofides algo that provides "approximate polynomial solution" to the "exponential" Traveling Salesman Problem

Please write your thoughts on this, if any

Madhukiran

[puneetkumarsingh]

From 2:50, So when are we going to poke around other boxes? Eagerly waiting for those.

[chanwoolee]

Awesome and well made. Worth spreading more.

[sharmanalin]

Great video, but if we do greedy approach based on count of books each guy wants and start with minimum, we can solve it easily it O(n^2)?

Awesome!! Now I got it, cheers :D
I tried to go to your website, however it is down :(

[tiruarthanari]

Am I allowed to use these videos n my YouTube on an advanced topic?

[TheSalaho]

Sir thanks for sharing the lesson, I have a question how can I limit the matchers dynamically, meaning if I want to match stock buyers to brokers each buyer have a volume ask N and a number x of brokers he's willing to work with, how this can be modeled?

[akashbhalotia]

Your videos are awesome. Thanks a lot :)

[boohoo]

Ok but what do you in a certain scenario(where all capacities are 0, 1) with the 2nd person(top to bottom) and the 4th person, they both lead to book 3 but book 3 should only be assigned to the 4th right. Well, if you were to traverse the algorithm using a DFS it would start at the 1st person then go to the 2nd book and augment, and then to the 2nd person it would skip the 2nd book since capacity == 0 and would go down to the 3rd book and augment that entire path. However, the 4th person needs to be assigned to the third book but the capacity of the book is already filled. You could think of removing the flow from that line and set the edge from 2nd person to 3rd book to visited, so that it won't visit it again and on next iteration it would skip to the 4th book, and the 4th person can be assigned the book. But I could only see a case where it can be possible to set a new flow path from the 4th person to the 3rd after a For loop break where the conditional is that an edge needs to have a capacity >0 and not be visited. However, even if there was some logic after a for loop break to reset a path, that logic would apply to every person since eventually they won't have valid edges too.

Could someone help me even a little with this, because it's really preventing me from seeing how the case with (0, 1) capacity edges will work in code, or maybe I should go look at more flow algorithms.

[shriharikulkarni]

Hi William, Is bipartite graph a connected graph ? In a graph of n independent nodes with no edges at all, we can color them with only 1 color.

[ronstudios]

Thanks! This really helped me with foobar!

[ronstudios]

Could you try and explain the edmond Blossom algorithm for unweighted graphs?

[DarkLordAli]

really great videos, but I recommend watching them at 1.5x playback speed :D

[_schnelli]

If I watched this before my assignment would have been much easier