A New Approach to Stable Matching Problems
Author:
- Ashok SubramanianASAshok Subramanian
- 1 August 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (4) , 671-700
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.Keywords
This publication has 19 references indexed in Scilit:
- A new fixed point approach for stable networks and stable marriagesJournal of Computer and System Sciences, 1992
- The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable AssignmentsSIAM Journal on Computing, 1988
- A simple parallel algorithm for finding a satisfying truth assignment to a 2-cnf formulaInformation Processing Letters, 1988
- Three Fast Algorithms for Four Problems in Stable MarriageSIAM Journal on Computing, 1987
- The Complexity of Counting Stable MarriagesSIAM Journal on Computing, 1986
- An efficient algorithm for the “stable roommates” problemJournal of Algorithms, 1985
- Some remarks on the stable matching problemDiscrete Applied Mathematics, 1985
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- The monotone and planar circuit value problems are log space complete for PACM SIGACT News, 1977
- College Admissions and the Stability of MarriageThe American Mathematical Monthly, 1962