The Generalized Popular Condensation Problem

DOI10.1007/978-3-319-13075-0_48zbMath1435.91129OpenAlexW2258787864MaRDI QIDQ2942664

Wei-Yin Lin, Yen-Wei Wu, Hung-Lung Wang, Kun-Mao Chao

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13075-0_48

zbMATH Keywords

bipartite graphNP-hardnesssatisfying assignmentpopular matching problempreference listlocal applicantmatching mappingmaximum match

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Matching models (91B68)

Related Items

The popular matching and condensation problems under matroid constraints, Popular Matchings with Ties and Matroid Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Popular matchings with variable item copies
• Popular matchings: structure and algorithms
• Optimal popular matchings
• Matching theory
• Popular matchings in the stable marriage problem
• Popularity at minimum cost
• An Optimal Algorithm for the Popular Condensation Problem
• Bounded Unpopularity Matchings
• Popular Matchings
• Popular Matchings in the Marriage and Roommates Problems
• Weighted Popular Matchings
• Popular and Clan-Popular b-Matchings
• Near-Popular Matchings in the Roommates Problem
• The complexity of satisfiability problems
• Popular Matchings in the Capacitated House Allocation Problem
• The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Dynamic Matching Markets and Voting Paths