On the Likely Number of Solutions for the Stable Marriage Problem
From MaRDI portal
Publication:3557497
DOI10.1017/S0963548308009607zbMath1200.05174MaRDI QIDQ3557497
Publication date: 23 April 2010
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548308009607
68Q25: Analysis of algorithms and problem complexity
60C05: Combinatorial probability
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
91B68: Matching models
Related Items
On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women, On random exchange-stable matchings, Two-sided matching markets with strongly correlated preferences, On random stable matchings: cyclic ones with strict preferences and two-sided ones with partially ordered preferences, One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences, Disjoint stable matchings in linear time
Cites Work
- Unnamed Item
- Unnamed Item
- The ``stable roommates problem with random preferences
- On likely solutions of a stable marriage problem
- The Average Number of Stable Matchings
- The Complexity of Counting Stable Marriages
- On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
- An upper bound for the solvability probability of a random stable roommates instance
- An analysis of the stable marriage assignment algorithm
- Stable husbands
- College Admissions and the Stability of Marriage