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.