A New Approach to Stable Matching Problems

Author:
  • ASAshok Subramanian
    Ashok Subramanian

Abstract
It is shown 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.

This publication has 19 references indexed in Scilit: