THE STRUCTURE OF THE STABLE ROOMMATE PROBLEM - EFFICIENT REPRESENTATION AND ENUMERATION OF ALL STABLE ASSIGNMENTS

被引:32
作者
GUSFIELD, D
机构
[1] Univ of California, United States
关键词
Mathematical Techniques--Combinatorial Mathematics;
D O I
10.1137/0217048
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The stable roommates problem is a well-known problem of matching 2n people into disjoint pairs to achieve a certain type of stability. The problem strictly generalizes the better-known stable marriage problem. It has been previously shown that the set of stable marriages, for a given instance, can be compactly represented and this representation has been exploited to yield a number of very efficient algorithms concerned with stable marriage. We generalize the structure of the stable marriages to obtain two efficiently computed, small, implicit representations of the set of all stable roommate assignments, for any given instance. One representation is a partial order II on O(n2) elements such that the stable assignments are in one-one correspondence with certain easily recognized subsets of II. We also give an algorithm to generate each stable assignment for any given instance in O(n2) time per assignment. Finally, we give a succinct characterization of the set of all 'stable pairs', those pairs of people who are roommates in at least one stable assignment, and we give an O(n3log n) time algorithm to find them all.
引用
收藏
页码:742 / 769
页数:28
相关论文
共 18 条
[1]   SOME REMARKS ON THE STABLE MATCHING PROBLEM [J].
GALE, D ;
SOTOMAYOR, M .
DISCRETE APPLIED MATHEMATICS, 1985, 11 (03) :223-232
[2]   COLLEGE ADMISSIONS AND STABILITY OF MARRIAGE [J].
GALE, D ;
SHAPLEY, LS .
AMERICAN MATHEMATICAL MONTHLY, 1962, 69 (01) :9-&
[3]   EVERY FINITE DISTRIBUTIVE LATTICE IS A SET OF STABLE MATCHINGS FOR A SMALL STABLE MARRIAGE INSTANCE [J].
GUSFIELD, D ;
IRVING, R ;
LEATHER, P ;
SAKS, M .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1987, 44 (02) :304-309
[4]   3 FAST ALGORITHMS FOR 4 PROBLEMS IN STABLE MARRIAGE [J].
GUSFIELD, D .
SIAM JOURNAL ON COMPUTING, 1987, 16 (01) :111-128
[5]  
GUSFIELD D, 1985, TR407 YAL U DEP COMP
[6]  
GUSFIELD D, 1986, 482 YAL U DEP COMP S
[7]  
GUSFIELD D, 1985, TR435 YAL U DEP COMP
[8]  
IRI M, 1984, PROGR COMBINATORIAL
[9]  
Irving R., 1986, CSC86R5 U GLASG DEP
[10]   AN EFFICIENT ALGORITHM FOR THE OPTIMAL STABLE MARRIAGE [J].
IRVING, RW ;
LEATHER, P ;
GUSFIELD, D .
JOURNAL OF THE ACM, 1987, 34 (03) :532-543