CFP last date
20 June 2024
Reseach Article

Preserving the Basic Property of Stable Matching by Deleting a Pair

Published on December 2013 by Ekta Gupta, Kalyani, Nitin
International Conference on Distributed Computing and Internet Technology 2014
Foundation of Computer Science USA
ICDCIT2014 - Number 1
December 2013
Authors: Ekta Gupta, Kalyani, Nitin
2049f0ce-83e7-4235-ba3c-f54f31253b0c

Ekta Gupta, Kalyani, Nitin . Preserving the Basic Property of Stable Matching by Deleting a Pair. International Conference on Distributed Computing and Internet Technology 2014. ICDCIT2014, 1 (December 2013), 14-18.

@article{
author = { Ekta Gupta, Kalyani, Nitin },
title = { Preserving the Basic Property of Stable Matching by Deleting a Pair },
journal = { International Conference on Distributed Computing and Internet Technology 2014 },
issue_date = { December 2013 },
volume = { ICDCIT2014 },
number = { 1 },
month = { December },
year = { 2013 },
issn = 0975-8887,
pages = { 14-18 },
numpages = 5,
url = { /proceedings/icdcit2014/number1/14379-1303/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 International Conference on Distributed Computing and Internet Technology 2014
%A Ekta Gupta
%A Kalyani
%A Nitin
%T Preserving the Basic Property of Stable Matching by Deleting a Pair
%J International Conference on Distributed Computing and Internet Technology 2014
%@ 0975-8887
%V ICDCIT2014
%N 1
%P 14-18
%D 2013
%I International Journal of Computer Applications
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
  1. D. Gale, L. S. Shapley 1962 College admissions and the stability of marriage, The American Mathematical Monthly 69, pp. 9–15.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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
  7. D. Gusfield, R. W. Irving, 1989 The stable marriage problem: structure and algorithms, The MIT Press, Cambridge, MA.
  8. S. S. Tseng and R. C. T. Lee 1984 A Parallel Algorithm to solve the Stable Marriage Problem, BIT 24:308, 316.
  9. Michael J. Quinn 1985 A note on Two parallel Algorithms to solve the stable marriage problem, BIT 25:473.
  10. Jesper Larsen 1997 A Parallel Approach to Stable Marriage Problem.
  11. 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
Index Terms

Computer Science
Information Sciences

Keywords

Stable Matching Stable Marriage Complete Strictly Ordered Rank Score Matching Set Happiness.