标题: 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
显示于类别:Articles


文件中的档案:

  1. A1990EX83000006.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.