On the Likely Number of Solutions for the Stable Marriage Problem

DOI10.1017/S0963548308009607zbMath1200.05174MaRDI QIDQ3557497

Craig Lennon, Boris G. Pittel

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

Mathematics Subject Classification ID

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