caa a22 4500 465821278 CHVBK 20180323112136.0 cr unu---uuuuu 170327e19901201xx s 000 0 eng 10.1007/BF01933211 doi (NATIONALLICENCE)springer-10.1007/BF01933211 Tan Jimmy Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, Republic of China aut A maximum stable matching for the roommates problem [Elektronische Daten] [Jimmy Tan] The stable roommates problem is that of matchingn people inton/2 disjoint pairs so that no two persons, who are not paired together, both prefer each other to their respective mates under the matching. Such a matching is called "a complete stable matching”. It is known that a complete stable matching may not exist. Irving proposed anO(n 2) algorithm that would find one complete stable matching if there is one, or would report that none exists. Since there may not exist any complete stable matching, it is natural to consider the problem of finding a maximum stable matching, i.e., a maximum number of disjoint pairs of persons such that these pairs are stable among themselves. In this paper, we present anO(n 2) algorithm, which is a modified version of Irving's algorithm, that finds a maximum stable matching. BIT Foundations, 1990 F2.2 nationallicence G2.1 nationallicence stable roommates problem nationallicence stable matching nationallicence maximum stable matching nationallicence algorithms nationallicence BIT Numerical Mathematics Kluwer Academic Publishers 30/4(1990-12-01), 631-640 0006-3835 30:4<631 1990 30 10543 https://doi.org/10.1007/BF01933211 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01933211 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Tan Jimmy Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, Republic of China aut NATIONALLICENCE 773 0- BIT Numerical Mathematics Kluwer Academic Publishers 30/4(1990-12-01), 631-640 0006-3835 30:4<631 1990 30 10543 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer