A maximum stable matching for the roommates problem

DOI10.1007/BF01933211zbMath0711.68051OpenAlexW1968154277MaRDI QIDQ922705

Jimmy J. M. Tan

Publication date: 1990

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01933211

zbMATH Keywords

stable roommates problemstable matchingmaximum stable matching

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Parallel algorithms in computer science (68W10)

Related Items

A new solution concept for the roommate problem: \(\mathcal{Q}\)-stable matchings ⋮ Analysis of stochastic matching markets ⋮ Stability against robust deviations in the roommate problem ⋮ Consistent enlargements of the core in roommate problems ⋮ Balancing stability and efficiency in team formation as a generalized roommate problem ⋮ Robust and approximately stable marriages under partial information ⋮ Unilateral stability in matching problems ⋮ Weak stability against robust deviations and the bargaining set in the roommate problem ⋮ Absorbing sets in roommate problems ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Efficient stabilization of cooperative matching games ⋮ Random paths to \(P\)-stability in the roommate problem ⋮ Impossibilities for roommate problems

Cites Work

• A necessary and sufficient condition for the existence of a complete stable matching
• An efficient algorithm for the “stable roommates” problem
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• College Admissions and the Stability of Marriage
• Unnamed Item