An algorithm for a super-stable roommates problem

DOI10.1016/j.tcs.2011.09.012zbMath1227.05233OpenAlexW2071068919MaRDI QIDQ650948

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

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

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

Related Items

Computing relaxations for the three-dimensional stable matching problem with cyclic preferences ⋮ The stable marriage problem with ties and restricted edges

Cites Work

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