AN EFFICIENT DEPTH-FIRST SEARCH ALGORITHM FOR SOLVING THE MAXIMUM STABLE MARRIAGE PROBLEM WITH TIES AND INCOMPLETE LISTS
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 th...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Trường Đại học Vinh
2024-12-01
|
| Series: | Tạp chí Khoa học |
| Subjects: | |
| Online Access: | https://vujs.vn//api/view.aspx?cid=fd776f0d-0fc0-41a1-b599-0de52c8267d6 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841550775808950272 |
|---|---|
| author | Le Quoc Anh, Hoang Huu Viet Dinh Van Nam |
| author_facet | Le Quoc Anh, Hoang Huu Viet Dinh Van Nam |
| author_sort | Le Quoc Anh, Hoang Huu Viet |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-77ffbc81fcc2469ab10c3cb1b2138eaa |
| institution | Kabale University |
| issn | 1859-2228 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | Trường Đại học Vinh |
| record_format | Article |
| series | Tạp chí Khoa học |
| spelling | doaj-art-77ffbc81fcc2469ab10c3cb1b2138eaa2025-01-10T03:29:59ZengTrường Đại học VinhTạp chí Khoa học1859-22282024-12-01534A11212310.56824/vujs.2024a146aAN EFFICIENT DEPTH-FIRST SEARCH ALGORITHM FOR SOLVING THE MAXIMUM STABLE MARRIAGE PROBLEM WITH TIES AND INCOMPLETE LISTSLe Quoc Anh, Hoang Huu Viet0Dinh Van Nam1nstitute of Engineering and Technology, Vinh University, Nghe An, VietnamFaculty of Pedagogy, Ha Tinh University, Ha Tinh, VietnamThis 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.https://vujs.vn//api/view.aspx?cid=fd776f0d-0fc0-41a1-b599-0de52c8267d6depth-first searchgale-shapley algorithmstable matchingstable marriage problemties and incomplete lists |
| spellingShingle | Le Quoc Anh, Hoang Huu Viet Dinh Van Nam AN EFFICIENT DEPTH-FIRST SEARCH ALGORITHM FOR SOLVING THE MAXIMUM STABLE MARRIAGE PROBLEM WITH TIES AND INCOMPLETE LISTS Tạp chí Khoa học depth-first search gale-shapley algorithm stable matching stable marriage problem ties and incomplete lists |
| title | AN EFFICIENT DEPTH-FIRST SEARCH ALGORITHM FOR SOLVING THE MAXIMUM STABLE MARRIAGE PROBLEM WITH TIES AND INCOMPLETE LISTS |
| title_full | AN EFFICIENT DEPTH-FIRST SEARCH ALGORITHM FOR SOLVING THE MAXIMUM STABLE MARRIAGE PROBLEM WITH TIES AND INCOMPLETE LISTS |
| title_fullStr | AN EFFICIENT DEPTH-FIRST SEARCH ALGORITHM FOR SOLVING THE MAXIMUM STABLE MARRIAGE PROBLEM WITH TIES AND INCOMPLETE LISTS |
| title_full_unstemmed | AN EFFICIENT DEPTH-FIRST SEARCH ALGORITHM FOR SOLVING THE MAXIMUM STABLE MARRIAGE PROBLEM WITH TIES AND INCOMPLETE LISTS |
| title_short | AN EFFICIENT DEPTH-FIRST SEARCH ALGORITHM FOR SOLVING THE MAXIMUM STABLE MARRIAGE PROBLEM WITH TIES AND INCOMPLETE LISTS |
| title_sort | efficient depth first search algorithm for solving the maximum stable marriage problem with ties and incomplete lists |
| topic | depth-first search gale-shapley algorithm stable matching stable marriage problem ties and incomplete lists |
| url | https://vujs.vn//api/view.aspx?cid=fd776f0d-0fc0-41a1-b599-0de52c8267d6 |
| work_keys_str_mv | AT lequocanhhoanghuuviet anefficientdepthfirstsearchalgorithmforsolvingthemaximumstablemarriageproblemwithtiesandincompletelists AT dinhvannam anefficientdepthfirstsearchalgorithmforsolvingthemaximumstablemarriageproblemwithtiesandincompletelists AT lequocanhhoanghuuviet efficientdepthfirstsearchalgorithmforsolvingthemaximumstablemarriageproblemwithtiesandincompletelists AT dinhvannam efficientdepthfirstsearchalgorithmforsolvingthemaximumstablemarriageproblemwithtiesandincompletelists |