<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>7924</REFNUM><AUTHORS><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>O'Malley,G.</AUTHOR></AUTHORS><YEAR>2005</YEAR><TITLE>Modelling and solving the stable marriage problem using constraint programming</TITLE><PLACE_PUBLISHED>DCS Tech Report</PLACE_PUBLISHED><PUBLISHER>N/A</PUBLISHER><ISBN>TR-2005-192</ISBN><LABEL>Manlove:2005:7924</LABEL><ABSTRACT>We study the Stable Marriage problem (SM), which is a combinatorial problem that arises in many practical applications. We present two new models of an instance I of SM with n men and n women as an instance J of a Constraint Satisfaction Problem. We prove that establishing arc consistency in J yields the same structure as given by the established Extended Gale/Shapley algorithm for SM as applied to I. Consequently, a solution (stable matching) of I can be derived without search. Furthermore we show that, in both encodings, <i>all</i> stable matchings in I may be enumerated in a failure-free manner. Our first encoding is of O(n^3) complexity and is very natural, whilst our second model, of O(n^2) complexity (which is optimal), is a development of the Boolean encoding in [6], establishing a greater level of structure. </ABSTRACT></RECORD></RECORDS></XML>