The generalized popular condensation problem

DOI10.1007/978-3-319-13075-0_48MaRDI QIDQ2942664zbMATH OpenOpenAlexFDO

Authors Yen-Wei Wu, Wei-Yin Lin, 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 graphlocal applicantmatching mappingmaximum matchNP-hardnesspopular matching problempreference listsatisfying assignment

Mathematics Subject Classification ID

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

Recommendations

• An optimal algorithm for the popular condensation problem
• The popular matching and condensation problems under matroid constraints
• The popular matching and condensation problems under matroid constraints

Cites work

• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An optimal algorithm for the popular condensation problem
• Bounded Unpopularity Matchings
• Dynamic Matching Markets and Voting Paths
• scientific article; zbMATH DE number 863471 (Why is no real title available?)
• Matching theory
• Near-popular matchings in the roommates problem
• Optimal popular matchings
• Popular and Clan-Popular b-Matchings
• Popular Matchings
• Popular Matchings in the Capacitated House Allocation Problem
• Popular matchings in the marriage and roommates problems
• Popular matchings in the stable marriage problem
• Popular matchings with variable item copies
• Popular matchings: structure and algorithms
• Popularity vs maximum cardinality in the stable marriage setting
• The complexity of satisfiability problems
• The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences
• Weighted Popular Matchings

Cited in

(6)

• An optimal algorithm for the popular condensation problem
• The popular matching and condensation problems under matroid constraints
• The popular matching and condensation problems under matroid constraints
• Popular matchings with ties and matroid constraints
• Plurality in spatial voting games with constant
• Modifying an instance of the super-stable matching problem

This page was built for publication: The generalized popular condensation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942664)