On a generalization of the stable roommates problem

Katarina Cechlarova, Tamás Fleiner


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 b-matchings as a by-product of the justification of the algorithm.

Bibtex entry:

AUTHOR = {Cechlarova, Katarina and Fleiner, Tam{\'a}s},
TITLE = {On a generalization of the stable roommates problem},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2003},
NUMBER = {TR-2003-03}

Last modification: 21.9.2017. Please email your comments to Tamás Király!