Report Number: CS-TR-89-1275
Institution: Stanford University, Department of Computer Science
Title: A new approach to stable matching problems
Author: Subramanian, Ashok
Date: August 1989
Abstract: We show that Stable Matching problems are the same as problems about stable configurations of X-networks. Consequences include easy proofs of old theorems, a new simple algorithm for finding a stable matching, an understanding of the difference between Stable Marriage and Stable Roommates, NP-completeness of Three-party Stable Marriage, CC-completeness of several Stable Matching problems, and a fast parallel reduction from the Stable Marriage problem to the Assignment problem.
http://i.stanford.edu/pub/cstr/reports/cs/tr/89/1275/CS-TR-89-1275.pdf