Maintaining Near-Popular Matchings

DOI10.1007/978-3-662-47666-6_40zbMath1440.68181MaRDI QIDQ3449500

Martin Hoefer, Sayan Bhattacharya, Lisa Wagner, Telikepalli Kavitha, Chien-Chung Huang

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/92712/1/WRAP-maintaining-near-popular-matchings-Bhattachaya-2015.pdf

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

91B68: Matching models

Related Items

Quasi-Popular Matchings, Optimality, and Extended Formulations, The dynamics of rank-maximal and popular matchings, Dynamic rank-maximal and popular matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random paths to stability in the roommate problem
• Local matching dynamics in social networks
• Maintaining a large matching and a small vertex cover
• Matching Dynamics with Constraints
• Locally Stable Marriage with Strict Preferences
• Uncoordinated Two-Sided Matching Markets
• Random Paths to Stability in Two-Sided Matching
• Popular Matchings
• Popular Matchings in the Marriage and Roommates Problems
• Near-Popular Matchings in the Roommates Problem
• Algorithmics of Matching Under Preferences
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
• Voting Paths
• The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences
• Fully Dynamic Maximal Matching in O (log n) Update Time