ACM Transactions on Algorithms · 2005 · 73 citations · 14 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsParallel AlgorithmsCombinatorial OptimizationGraph AlgorithmsGraph TheoryMatching TheoryBipartite MatchingExistence Of Stable MatchingsGraph MatchingMany-to-many MatchingMatching AlgorithmsMatching ProblemsStable Roommates Problem
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.
14