On the Likely Number of Solutions for the Stable Marriage Problem

DOI10.1017/S0963548308009607zbMath1200.05174OpenAlexW2131227897MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Related Items (6)

Two-sided matching markets with strongly correlated preferences ⋮ On random exchange-stable matchings ⋮ Disjoint stable matchings in linear time ⋮ 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 ⋮ On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women

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

This page was built for publication: On the Likely Number of Solutions for the Stable Marriage Problem