An algorithm for a super-stable roommates problem

DOI10.1016/J.TCS.2011.09.012MaRDI QIDQ650948zbMATH OpenOpenAlexFDO

Authors Tamás Fleiner, Robert W. Irving, David F. Manlove

Publication date 7 December 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.09.012

zbMATH Keywords

polynomial time algorithmstable roommates problemstable marriages

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Recommendations

• An efficient algorithm for the “stable roommates” problem
• Efficient algorithms for generalized stable marriage and roommates problems
• The Stable Roommates Problem with Ties
• A generalization of the stable matching problem
• A maximum stable matching for the roommates problem

Cites work

• A necessary and sufficient condition for the existence of a complete stable matching
• An efficient algorithm for the “stable roommates” problem
• College Admissions and the Stability of Marriage
• Efficient algorithms for generalized stable marriage and roommates problems
• NP-complete stable matching problems
• On a lemma of Scarf.
• The Stable Roommates Problem with Ties
• The stable marriage problem with restricted pairs.

Cited in

(7)

• A General Framework for Stable Roommates Problems using Answer Set Programming
• The stable marriage problem with ties and restricted edges
• An efficient algorithm for the “stable roommates” problem
• A maximum stable matching for the roommates problem
• Stable Roommates and Constraint Programming
• A note on roommate problems with a limited number of rooms
• Computing relaxations for the three-dimensional stable matching problem with cyclic preferences

This page was built for publication: An algorithm for a super-stable roommates problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650948)