A MAXIMUM STABLE MATCHING FOR THE ROOMMATES PROBLEM

檔案

日期

1990

作者

期刊名稱

BIT

摘要

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

TAN, J. (1990). A MAXIMUM STABLE MATCHING FOR THE ROOMMATES PROBLEM. BIT, 30(4), 631–640. https://doi.org/10.1007/BF01933211

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/4210