| |
|
|
Abstract: This paper deals with the stable b-matching problem on general multigraphs. We generalize the notion of singular and dual rotation and establish a one-one correspondence between stable b-matchings and certain sets of rotations. This correspondence is used to find all stable edges and a minimum regret stable b-matching in polynomial time. We also recall the NP-completeness of the egalitarian stable b-matching problem. Contact the authors: viera.borbelova@upjs.sk, katarina.cechlarova@upjs.sk Download PDF version of the preprint. |