標題: A MAXIMUM STABLE MATCHING FOR THE ROOMMATES PROBLEM
作者: TAN, JJM
資訊工程學系
Department of Computer Science
關鍵字: STABLE ROOMMATES PROBLEM;STABLE MATCHING;MAXIMUM STABLE MATCHING;ALGORITHMS
公開日期: 1990
摘要: The stable roommates problem is that of matching n people into n/2 disjoint pairs so that no two persons, who are not paired together, both prefer each other to their respective mates under the matching. Such a matching is called "a complete stable matching". It is known that a complete stable matching may not exist. Irving proposed an O(n2) algorithm that would find one complete stable matching if there is one, or would report that none exists. Since there may not exist any complete stable matching, it is natural to consider the problem of finding a maximum stable matching, i.e., a maximum number of disjoint pairs of persons such that these pairs are stable among themselves. In this paper, we present an O(n2) algorithm, which is a modified version of Irving's algorithm, that finds a maximum stable matching.
URI: http://hdl.handle.net/11536/4210
http://dx.doi.org/10.1007/BF01933211
ISSN: 0006-3835
DOI: 10.1007/BF01933211
期刊: BIT
Volume: 30
Issue: 4
起始頁: 631
結束頁: 640
顯示於類別:期刊論文


文件中的檔案:

  1. A1990EX83000006.pdf