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 条
[11]  
McVitie D. G., 1970, BIT (Nordisk Tidskrift for Informationsbehandling), V10, P295, DOI 10.1007/BF01934199
[12]   STABLE MARRIAGE PROBLEM [J].
MCVITIE, DG ;
WILSON, LB .
COMMUNICATIONS OF THE ACM, 1971, 14 (07) :486-&
[13]   Stable allocations and partially ordered sets [J].
Mourtos, Ioannis ;
Samaris, Michalis .
DISCRETE OPTIMIZATION, 2022, 46
[14]   MAXIMAL CLOSURE OF A GRAPH AND APPLICATIONS TO COMBINATORIAL PROBLEMS [J].
PICARD, JC .
MANAGEMENT SCIENCE, 1976, 22 (11) :1268-1272
[15]  
Plya G., 1983, Notes on Introductory Combinatorics, P55, DOI [10.1007/978-1-4757-1101-16, DOI 10.1007/978-1-4757-1101-16]
[16]   THE COMPLEXITY OF COUNTING CUTS AND OF COMPUTING THE PROBABILITY THAT A GRAPH IS CONNECTED [J].
PROVAN, JS ;
BALL, MO .
SIAM JOURNAL ON COMPUTING, 1983, 12 (04) :777-788
[17]   STABLE MATCHINGS, OPTIMAL ASSIGNMENTS, AND LINEAR-PROGRAMMING [J].
ROTH, AE ;
ROTHBLUM, UG ;
VANDEVATE, JH .
MATHEMATICS OF OPERATIONS RESEARCH, 1993, 18 (04) :803-828
[18]   CHARACTERIZATION OF STABLE MATCHINGS AS EXTREME-POINTS OF A POLYTOPE [J].
ROTHBLUM, UG .
MATHEMATICAL PROGRAMMING, 1992, 54 (01) :57-67
[19]  
Schrijver A, 2003, Combinatorial Optimization-Polyhedra and Efficiency
[20]   A NECESSARY AND SUFFICIENT CONDITION FOR THE EXISTENCE OF A COMPLETE STABLE MATCHING [J].
TAN, JJM .
JOURNAL OF ALGORITHMS, 1991, 12 (01) :154-178
123