On the Set of Stable Matchings in a Bipartite Graph

被引：0
作者：
Karzanov, A. V. [1 ]
机构：
[1] Russian Acad Sci, Cent Inst Econ & Math, Moscow 117418, Russia
来源：
COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS | 2023年 / 63卷 / 08期
关键词：
stable matching; poset of rotations; stable matching of minimum cost; median stable matching; EFFICIENT ALGORITHM; COMPLEXITY;
D O I：
10.1134/S0965542523080080
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The topic of stable matchings (marriages) in bipartite graphs gained popularity beginning from the appearance of the classical Gale and Shapley work. In this paper, a detailed review of selected and other related statements in this field that describe structured, polyhedral, and algorithmic properties of such objects and their sets accompanied by short proofs is given.
引用
收藏
页码：1540 / 1556
页数：17
相关论文
共 24 条
[1]   The stable allocation (or ordinal transportation) problem (vol 27, pg 485, 2002) [J].
Baïou, M ;
Balinski, M .
MATHEMATICS OF OPERATIONS RESEARCH, 2002, 27 (04) :662-680
[2]   Faster Algorithms for Stable Allocation Problems [J].
Dean, Brian C. ;
Munshi, Siddharth .
ALGORITHMICA, 2010, 58 (01) :59-81
[3]   COLLEGE ADMISSIONS AND STABILITY OF MARRIAGE [J].
GALE, D ;
SHAPLEY, LS .
AMERICAN MATHEMATICAL MONTHLY, 1962, 69 (01) :9-&
[4]  
Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
[5]   3 FAST ALGORITHMS FOR 4 PROBLEMS IN STABLE MARRIAGE [J].
GUSFIELD, D .
SIAM JOURNAL ON COMPUTING, 1987, 16 (01) :111-128
[6]   AN EFFICIENT ALGORITHM FOR THE OPTIMAL STABLE MARRIAGE [J].
IRVING, RW ;
LEATHER, P ;
GUSFIELD, D .
JOURNAL OF THE ACM, 1987, 34 (03) :532-543
[7]   AN EFFICIENT ALGORITHM FOR THE STABLE ROOMMATES PROBLEM [J].
IRVING, RW .
JOURNAL OF ALGORITHMS, 1985, 6 (04) :577-595
[8]   THE COMPLEXITY OF COUNTING STABLE MARRIAGES [J].
IRVING, RW ;
LEATHER, P .
SIAM JOURNAL ON COMPUTING, 1986, 15 (03) :655-667
[9]   ON CLOSED-SETS OF A DIRECTED GRAPH [J].
KARZANOV, AV .
USSR COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS, 1984, 24 (06) :197-200
[10]  
Knuth D., 1976, Mariages stables
123