Maintaining Near-Popular Matchings

DOI10.1007/978-3-662-47666-6_40zbMath1440.68181OpenAlexW1910074032MaRDI 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

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Matching models (91B68)

Related Items (4)

Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ Online 2-stage stable matching ⋮ Dynamic rank-maximal and popular matchings ⋮ The dynamics of 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

This page was built for publication: Maintaining Near-Popular Matchings