Jointly stable matchings

DOI10.1007/s10878-019-00402-4zbMath1425.90099OpenAlexW2924910218MaRDI QIDQ2424832

Shuichi Miyazaki, Kazuya Okamoto

Publication date: 25 June 2019

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8224/

zbMATH Keywords

NP-completenesslinear time algorithmstable marriage problemstable matching

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (3)

Stable matching with multilayer approval preferences: approvals can be harder than strict preferences ⋮ Stable matching with multilayer approval preferences: approvals can be harder than strict preferences ⋮ Strongly stable and maximum weakly stable noncrossing matchings

Cites Work

• Unnamed Item
• Some remarks on the stable matching problem
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Stable marriage and indifference
• Concerning the maximum number of stable matchings in the stable marriage problem
• A polynomial-time algorithm for the bistable roommates problem
• The structure of stable marriage with indifference
• The set of super-stable marriages forms a distributive lattice
• Bistable versions of the marriages and roommates problems
• Stable Matching with Uncertain Linear Preferences
• The Complexity of Counting Stable Marriages
• On the Complexity of Timetable and Multicommodity Flow Problems
• A simply exponential upper bound on the maximum number of stable matchings
• Algorithmics of Matching Under Preferences
• College Admissions and the Stability of Marriage

This page was built for publication: Jointly stable matchings