A CHARACTERIZATION OF GRAPHS THAT ENSURE THE EXISTENCE OF STABLE MATCHINGS

被引：10

作者：

ABELEDO, H ^{[1
]}

ISAAK, G ^{[1
]}

机构：

[1] DARTMOUTH COLL,DEPT MATH,HANOVER,NH 03755

来源：

MATHEMATICAL SOCIAL SCIENCES | 1991年 / 22卷 / 01期

基金：

美国国家科学基金会;

关键词：

STABLE MATCHING; STABLE MARRIAGE; GRAPH THEORY;

D O I：

10.1016/0165-4896(91)90069-4

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

In this note we characterize sets of mutually acceptable pairs of individuals in the stable matching problem for which a stable matching exists under all preference profiles. In particular, our characterization asserts that the corresponding acceptability graph is bipartite.

引用

页码：93 / 96

页数：4

共 7 条

[1] ABELEDO H, 1990, UNPUB FRACTIONAL STA
[2] NONEXISTENCE OF STABLE THREESOME MATCHINGS
ALKAN, A
[J]. MATHEMATICAL SOCIAL SCIENCES, 1988, 16 (02) : 207 - 209
[3] COLLEGE ADMISSIONS AND STABILITY OF MARRIAGE
GALE, D
SHAPLEY, LS
[J]. AMERICAN MATHEMATICAL MONTHLY, 1962, 69 (01) : 9 - &
[4] Gusfield D., 1989, STABLE MARRIAGE PROB
[5] AN EFFICIENT ALGORITHM FOR THE STABLE ROOMMATES PROBLEM
IRVING, RW
[J]. JOURNAL OF ALGORITHMS, 1985, 6 (04) : 577 - 595
[6] Knuth D., 1976, MARIAGES STABLES
[7] ROTH A, 1990, EC MONOGRAPH SERIES

← 1 →