TR-2003-03

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:

@techreport{egres-03-03,

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

}