I was reading about online algorithms and bipartite matching.
I found an implementation that works fine on several websites (like geeksforgeeks). For the online version, I found this paper https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf
But there's one part that I don't understand.
In this paper, they refer to U (boys) as "on-line" which means data arrive sequentially (in real-time?) not all at once
While I can see how such case if frequent in real life, I fail to understand what kind of implementation could be used to demonstrate this...
I thought of the following
- Create a graph with girls
- add boys and define manually the girls they like via some sort of user input (input py/cin c++)
- solve(match) for the newly added boy according to rank(priority) and return to user input till no more girls are left or till user decides to stop?
In the online version do we assume a predefined limited number for both U and V(boys and girls)? or just for girls?
Is my suggestion correct? or did I misunderstand something?
Thanks in advance