USC
CSCI 570 -
Discussion 1
Unformatted text preview:
View Full Document
Discussion 1 1. Prove that every execution of the G-S algorithm (when men are proposing) results in the same stable matching regardless of the order in which men propose. 2. Prove that when we run the G-S algorithm with men proposing, women end up with their worst valid partners. 3. True or False: In every stable matching that Gale–Shapley algorithm may end up with when men propose, there is a man who is matched to his highest-ranked woman. 4. In a connected bipartite graph, is the bipartition unique? Justify your
View Full Document
Unlocking...