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 answer
View Full Document
Unlocking...