On a generalization of the stable roommates problem

Katarı́na Cechlárová, Tamás Fleiner

ACM Transactions on Algorithms · 2005 · 73 citations · 14 references

Concepts

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.

References

14