How Do I Marry Thee? Let Me Count the Ways!
A stable marriage problem of size 2n is constructed which contains Θ(2n√n) stable matchings. This construction provides a new lower bound on the maximum number of stable matchings for problems of even size and is comparable to a known lower bound when the size is a power of 2. The method of construction makes use of special properties of the latin marriage problem, which we develop.
© 1995 Elsevier Science B.V.
Benjamin, A.T., Converse, C., & Krieger, H.A. (1995). How do I marry thee? Let me count the ways! Discrete Applied Mathematics, 59(3): 285-292. DOI: 10.1016/0166-218X(95)80006-P