<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>5830</REFNUM><AUTHORS><AUTHOR>Gent,I.P.</AUTHOR><AUTHOR>Irving,R.W.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>Prosser,P.</AUTHOR><AUTHOR>Smith,B.M.</AUTHOR></AUTHORS><YEAR>2001</YEAR><TITLE>A Constraint Programming Approach to the Stable Marriage Problem</TITLE><PLACE_PUBLISHED>Proceedings of CP 2001: The 7th International Conference on Principles and Practice of Constraint Programming, volume 2239 of Lecture Notes in Computer Science</PLACE_PUBLISHED><PUBLISHER>Springer Verlag</PUBLISHER><PAGES>225-239</PAGES><ISBN>3-540-42863-1</ISBN><LABEL>Gent:2001:5830</LABEL><ABSTRACT>The Stable Marriage problem (SM) is an extensively-studied combinatorial problem with many practical applications. In this paper we present two encodings of an instance I of SM as an instance J of a Constraint Satisfaction Problem. We prove that, in a precise sense, establishing arc consistency in J is equivalent to the action of the established Extended Gale/Shapley algorithm for SM on I. As a consequence of this, the man-optimal and woman-optimal stable matchings can be derived immediately. Furthermore we show that, in both encodings, all solutions of I may be enumerated in a failure-free manner. Our results indicate the applicability of Constraint Programming to the domain of stable matching problems in general, many of which are NP-hard.</ABSTRACT><NOTES>(c) Springer-Verlag <p></NOTES><URL>http://dx.doi.org/10.1007/3-540-45578-7_16</URL></RECORD></RECORDS></XML>