An efficient depth-first search algorithm for solving the maxi-mum stable marriage problem with ties and incomplete lists.

Abstract

This paper proposes an efficient depth-first search algorithm to solve the maximum stable marriage problem with ties and incomplete preference lists. The key idea of the algorithm is to initialize an empty matching and mark all men as unmatched. In each iteration, an unmatched man proposes to the most preferred woman on his rank list. If the woman is unmatched or prefers the proposing man over her current partner, she is assigned to the man, forming a new pair in the matching. Otherwise, she keeps her current partner and rejects the proposing man. When a man is rejected by a woman, he becomes unmatched. The algorithm then recursively processes the next unmatched man until it either finds a complete matching or reaches a predefined maximum number of iterations. Experimental results on randomly generated datasets show that our algorithm is effective in producing high-quality solutions to the problem.