Home » Keyword index

stable roommates


Graph Theory » Basic G.T. » Matchings

Random stable roommates ★★

Author(s): Mertens

Conjecture   The probability that a random instance of the stable roommates problem on $ n \in 2{\mathbb N} $ people admits a solution is $ \Theta( n ^{-1/4} ) $.

Keywords: stable marriage; stable roommates

Posted by mdevos
updated February 26th, 2008
add new comment
Syndicate content