標題: A UNIFYING APPROACH TO THE STRUCTURES OF THE STABLE MATCHING PROBLEMS
作者: HSUEH, YC
交大名義發表
資訊工程學系
National Chiao Tung University
Department of Computer Science
公開日期: 1991
摘要: It is well-known that the structure of the set of stable marriages of a stable marriage instance can be represented as a finite distributive lattice and, conversely, every finite distributive lattice is a set of stable marriages for some stable marriage instance. Recently, Irving[12] and Gusfield [9] propose some representations of the set of all stable assignments for a given solvable instance of the stable roommates problem. In this paper, we will give a unifying approach to the structures of the stable marriage problem and the stable roommates problem. To achieve this purpose, we first study the duality in the structure of a stable marriage instance, then transform every stable roommates instance into a corresponding stable marriage instance and obtain the structure of the stable roommates instance directly from that of the corresponding stable marriage instance. The main results of this paper are: (1) There is a one-one correspondence between the set of stable marriages for a stable marriage instance and the set of feasible words of some Faigle geometry; (2) There is a one-one correspondence between the set of stable assignments for a stable roommates instance and the set of basic words of some Faigle geometry.
URI: http://hdl.handle.net/11536/3934
ISSN: 0898-1221
期刊: COMPUTERS & MATHEMATICS WITH APPLICATIONS
Volume: 22
Issue: 6
起始頁: 13
結束頁: 27
顯示於類別:期刊論文


文件中的檔案:

  1. A1991GJ46500002.pdf