<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>7981</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>Proceedings of the Fifth Workshop on Modelling and Solving Problems with Constraints, held at the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)</PLACE_PUBLISHED><PUBLISHER>N/A</PUBLISHER><PAGES>10-17</PAGES><LABEL>Manlove:2005:7981</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>