TR-2003-03

On a generalization of the stable roommates problem

Katarina Cechlarova, Tamás Fleiner



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 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 www.cs.elte.hu/egres}},
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!