Paper ID: 9166
Popular matchings: structure and algorithms
Proceedings of COCOON 2009, 15th Annual International Computing and Combinatorics Conference, Niagara Falls USA, July 2009, Lecture Notes in Computer Science vol. 5609
Page Numbers : 506-515
An instance of the popular matching problem (POP-M) consists of a set of applicants and a set of posts. Each applicant has a preference list that strictly ranks a subset of the posts. A matching M of applicants to posts is popular if there is no other matching M' such that more applicants prefer M' to M than prefer M to M'. This paper provides a characterization of the set of popular matchings for an arbitrary POP-M instance in terms of a structure called the switching graph, a directed graph computable in linear time from the preference lists. We show that the switching graph can be exploited to yield efficient algorithms for a range of associated problems, including
the counting and enumeration of the set of popular matchings and computing popular matchings that satisfy various additional optimality criteria. Our algorithms for computing such optimal popular matchings improve those described in a recent paper by Kavitha and Nasre.
Keywords: Matching, efficient algorithms