A New Approach to Stable Matching Problems

Ashok Subramanian

77 citations0/0 files storedSIAM Journal on Computing

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Voting Systems Complexity and Algorithms in Graphs Constraint Satisfaction and Optimization

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.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 77 citations exist upstream.

References

1962College Admissions and the Stability of Marriage 1962College Admissions and the Stability of Marriage 1991The Stable Marriage Problem: Structure and Algorithms 1985An efficient algorithm for the “stable roommates” problem 1985Some remarks on the stable matching problem 1987An efficient algorithm for the “optimal” stable marriage 1986The Complexity of Counting Stable Marriages 1987Three Fast Algorithms for Four Problems in Stable Marriage

Cited by

2005On a generalization of the stable roommates problem 2009Three-Sided Stable Matchings with Cyclic Preferences

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.