On a generalization of the stable roommates problem

Abstract

We consider two generalizations of the stable roommates problem: a) we allow parallel edges in the underlying graph, and b) we study a problem with multiple partners. We reduce both problems to the classical stable roommates problem and describe an extension of Irving's algorithm that solves the generalized problem efficiently. We give a direct proof of a recent result on the structure of stable many-to-many matchings (so called stable b -matchings) as a by-product of the justification of the algorithm.

Cite this work

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

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

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