Emanuel Olariu, Cristian Frasinaru

Popular matching and was extensively studied in recent years as an alternative to stable matchings.Both type of matchings are defined in the framework of Stable Marriage (SM) problem: in a givenbipartite graph G = (A;B;E) each vertex u has a strict order of preference on its neighborhood. Amatching M is popular, if for every matching M ‘ of G, the number of vertices that prefer M ‘ to M isat most the number of vertices which prefer M to M ‘. In this paper we prove that every maximumcardinality popular matching saturates the same set of vertices. This property is similar to that ofstable matchings: any such matching saturates the same set of vertices.

Full Document (PDF)


author = "Emanuel Olariu  and Cristian Fr{u a}sinaru",
title = "{Maximum cardinality popular matchings in the stable marriage problem}",
institution = "``Al.I.Cuza'' University of Ia{c s}i, 
                 Faculty of Computer Science",
year = "2015",
number = "TR 15-02",
note = "URL:http://www.infoiasi.ro/~tr/tr.pl.cgi"