<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>9011</REFNUM><AUTHORS><AUTHOR>McDermid,E.</AUTHOR><AUTHOR>Irving,R.W.</AUTHOR></AUTHORS><YEAR>2008</YEAR><TITLE>Popular Matchings: Structure and Algorithms</TITLE><PLACE_PUBLISHED>DCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><PAGES>1-20</PAGES><ISBN>TR-2008-292</ISBN><LABEL>McDermid:2008:9011</LABEL><KEYWORDS><KEYWORD>Matching</KEYWORD></KEYWORDS<ABSTRACT>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'. Abraham et al described a linear time algorithm to determine whether a popular matching exists for a given instance of POP-M, and if so to find a largest such matching. A number of variants and extensions of POP-M have recently been studied. 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, generation of a popular matching uniformly at random, finding all applicant-post pairs that can occur in a popular matching, 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.</ABSTRACT></RECORD></RECORDS></XML>