On a generalization of the stable roommates problem
K Cechlárová, T Fleiner - ACM Transactions on Algorithms (TALG), 2005 - dl.acm.org
ACM Transactions on Algorithms (TALG), 2005•dl.acm.org
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.
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.
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.
ACM Digital Library以上显示的是最相近的搜索结果。 查看全部搜索结果