Preserving the Basic Property of Stable Matching by Deleting a Pair
IJCA Proceedings on International Conference on Distributed Computing and Internet Technology 2014
© 2013 by IJCA Journal
ICDCIT 2014
Year of Publication: 2013
Ekta Gupta, Kalyani and Nitin. Article: Preserving the Basic Property of Stable Matching by Deleting a Pair. IJCA Proceedings on International Conference on Distributed Computing and Internet Technology 2014 ICDCIT-2014:14-18, December 2013. Full text available. BibTeX
@article{key:article,
author = {Ekta Gupta and Kalyani and Nitin},
title = {Article: Preserving the Basic Property of Stable Matching by Deleting a Pair},
journal = {IJCA Proceedings on International Conference on Distributed Computing and Internet Technology 2014},
year = {2013},
volume = {ICDCIT-2014},
pages = {14-18},
month = {December},
note = {Full text available}
}
Abstract
This paper describes the transition of a male-pessimal matching set to optimal when it is a man-oriented approach by deleting a pair from matching set considering the score based approach. A descriptive explanation of the proposed algorithm both in a sequential and parallel manner is given. The comparison based theoretical analysis shows that the best case of the algorithm is lower bound of n3.
References
- D. Gale, L. S. Shapley 1962 College admissions and the stability of marriage, The American Mathematical Monthly 69, pp. 9–15.
- Kazuo Iwama and Shuichi Miyazaki 2008 A survey of Stable Marriage Problem and Its Variants, International Conference on Informatics Education and Research for Knowledge Circulating Society, DOI 10. 1109/ICKS.
- A. T. Benjamin, C. Converse and H. A. Krieger 1995 "How Do I Marry Thee? Let Me Count The Ways", Discrete Applied Mathematics, Vol. 59, pp. 285-292.
- R. W. Irving, P. Leather and D. Gusfield 1987 "An efficient Algorithm for Optimal Stable Marriage", Journal of the ACM, Vol. 34, pp. 532-543.
- Chung-Piaw Teo, Jay Sethuraman, and Wee-Peng Tan 1999 Gale Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications, Springer IPCO'99, LNCS 1610, pp. 429-438.
- Huang, C. -C. Cheating by Men in Gale Shapley Stable Matching Algorithm. In the proceeding of ESA 2006, Zurich, Switzerland, 11-13 September 2006; pp. 418-431
- D. Gusfield, R. W. Irving, 1989 The stable marriage problem: structure and algorithms, The MIT Press, Cambridge, MA.
- S. S. Tseng and R. C. T. Lee 1984 A Parallel Algorithm to solve the Stable Marriage Problem, BIT 24:308, 316.
- Michael J. Quinn 1985 A note on Two parallel Algorithms to solve the stable marriage problem, BIT 25:473.
- Jesper Larsen 1997 A Parallel Approach to Stable Marriage Problem.
- Takao Inoshita, Robert W. Irvin, Kazuo Iwama, Shuichi Miyazaki and Takash Nagase 2013 Improving Man optimality Stable Matching by Minimum Change of Preference Lists, Algorithms, 6, 371-382; doi:10. 3390/a6020371