The stable marriage problem with master preference lists

DOI10.1016/J.DAM.2008.01.002zbMATH Open1175.05111OpenAlexW2028966815MaRDI QIDQ1005239FDOQ1005239

David F. Manlove, Robert W. Irving, Sandy Scott

Publication date: 9 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.01.002

zbMATH Keywords

NP-hardstable matchingstrongly stableweakly stablemaster list including tiesmaster preference liststrictly ordered master listsuper-stable

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some remarks on the stable matching problem
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• College Admissions and the Stability of Marriage
• Minimum Edge Dominating Sets
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Network flow and 2-satisfiability
• Student-project allocation with preferences over projects
• Hard variants of stable marriage.
• A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion
• Stable marriage and indifference
• Approximability results for stable marriage problems with ties.
• STACS 2004

Cited In (23)

• The hospitals/residents problem with lower quotas
• Stable matching of student-groups to dormitories
• Solving hard stable matching problems involving groups of similar agents
• Pairwise Preferences in the Stable Marriage Problem
• Satisfied two-sided matching: a method considering elation and disappointment of agents
• Maximum stable matching with one-sided ties of bounded length
• Maximum locally stable matchings
• Hedonic diversity games: a complexity picture with more than two colors
• Title not available (Why is that?)
• Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
• Stable Matchings with Ties, Master Preference Lists, and Matroid Constraints
• Stable matchings of teachers to schools
• The Price of Matching with Metric Preferences
• Recognizing when a preference system is close to admitting a master list
• Title not available (Why is that?)
• A simple matching domain with indifferences and a master list
• Almost mutually best in matching markets: rank gaps and size of the core
• Popular matchings with variable item copies
• Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
• Stable marriage with groups of similar agents
• Geometric stable roommates
• A Matroid Generalization of the Super-Stable Matching Problem
• Recognizing when a preference system is close to admitting a master list

This page was built for publication: The stable marriage problem with master preference lists

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