The stable marriage problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The stable marriage problem

Full text

Pdf (477 KB)

Source

Communications of the ACM archive
Volume 14 , Issue 7 (July 1971) table of contents

Pages: 486 - 490

Year of Publication: 1971

ISSN:0001-0782

Authors

D. G. McVitie	Software Science, Ltd., Wilmslow, Cheshire, England
L. B. Wilson	Univ. of Newcastle upon Tyne, England

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 30, Downloads (12 Months): 167, Citation Count: 10

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/362619.362631 What is a DOI?

ABSTRACT

The original work of Gale and Shapley on an assignment method using the stable marriage criterion has been extended to find all the stable marriage assignments. The algorithm derived for finding all the stable marriage assignments is proved to satisfy all the conditions of the problem. Algorithm 411 applies to this paper.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Gale, D., and Shapley, L.S. College admissions and the stability of marriage. Am. Math. Monthly 69 (1962), 9-15.
	2	D. G. McVitie , L. B. Wilson, Three procedures for the stable marriage problem, Communications of the ACM, v.14 n.7, p.491-492, July 1971 [doi>10.1145/362619.362632]

CITED BY 10

	Boris Pittel, On likely solutions of a stable matching problem, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.10-15, September 1992, Orlando, Florida, United States
	Owen Astrachan, On finding a stable roommate, job, or spouse: a case study crossing the boundaries of computer science courses, ACM SIGCSE Bulletin, v.24 n.1, p.107-112, March 1992
	Robert W. Irving , Paul Leather , Dan Gusfield, An efficient algorithm for the “optimal” stable marriage, Journal of the ACM (JACM), v.34 n.3, p.532-543, July 1987
	Stefan Edelkamp , Alberto Lluch Lafuente , Stefan Leue, Directed explicit model checking with HSF-SPIN, Proceedings of the 8th international SPIN workshop on Model checking of software, p.57-79, May 2001, Toronto, Ontario, Canada
	Donald E. Knuth , Rajeev Motwani , Boris Pittel, Stable husbands, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.397-404, January 22-24, 1990, San Francisco, California, United States
	Vânia M. F. Dias , Guilherme D. da Fonseca , Celina M. H. de Figueiredo , Jayme L. Szwarcfiter, The stable marriage problem with restricted pairs, Theoretical Computer Science, v.306 n.1-3, p.391-405, 5 September 2003
	Hongkun Zhao , Weiyi Meng , Clement Yu, Automatic extraction of dynamic record sections from search engine result pages, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Vipul Bansal , Aseem Agrawal , Varun S. Malhotra, Polynomial time algorithm for an optimal stable assignment with multiple partners, Theoretical Computer Science, v.379 n.3, p.317-328, June, 2007
	Enrique Alba , Francisco Chicano, Finding safety errors with ACO, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
	Christine Cheng , Eric McDermid , Ichiro Suzuki, A unified approach to finding good stable matchings in the hospitals/residents setting, Theoretical Computer Science, v.400 n.1-3, p.84-99, June, 2008

INDEX TERMS

Keywords:
assignment problems, assignment procedures, combinatorics, discrete mathematics, operational research, stable marriage problem, university entrance

Collaborative Colleagues:

D. G. McVitie: colleagues

L. B. Wilson: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player