Computational Complexity of Stable Marriage and Stable Roommates and Their Variants

2019/04/17 by Chen, Jiehua · 1 citation
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1904.08196

Abstract

This paper gives an overview on and summarizes existing complexity and algorithmic results of some variants of the Stable Marriage and the Stable Roommates problems. The last section defines a list of stable matching problems mentioned in the paper. If you find any corrections, suggestions, new or missing results, please send them to [email protected].

Cited by

• Perspectives on Unsolvability in Roommates Markets

Related

• Marriage and Roommate
• Stable marriage and roommate problems with individual-based stability
• Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
• Control in Stable Marriage and Stable Roommates: Complexity and Algorithms
• Multidimensional Stable Roommates with Master List