A necessary and sufficient condition for the existence of a complete stable matching

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

68W10: Parallel algorithms in computer science

Related Items

On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm, Hardness results for stable exchange problems, Planar Matchings for Weighted Straight Skeletons, Planar Matchings for Weighted Straight Skeletons, Hardness results for stable exchange problems, Analysis of stochastic matching markets, ``Almost stable matchings in the roommates problem with bounded preference lists, Dominance invariant one-to-one matching problems, When do stable roommate matchings exist? A review, Large roommate problem with non-transferable random utility, A model of partnership formation, Stochastic stability for roommate markets, An algorithm for a super-stable roommates problem, Unique stability in simple coalition formation games, Random paths to stability in the roommate problem, Smith and Rawls share a room: stability and medians, Core of coalition formation games and fixed-point methods, A maximum stable matching for the roommates problem, Rotations in the stable \(b\)-matching problem, Impossibilities for roommate problems, Efficient algorithms for generalized stable marriage and roommates problems, Representing roommates' preferences with symmetric utilities, On a lemma of Scarf., On the existence of stable roommate matchings, Stable marriage and roommates problems with restricted edges: complexity and approximability, Fractional solutions for capacitated NTU-games, with applications to stable matchings, A generalization of the stable matching problem, The integral stable allocation problem on graphs, The roommates problem revisited, The stable roommates problem with choice functions, Faster algorithms for stable allocation problems, Competitive equilibrium and singleton cores in generalized matching problems, Absorbing sets in roommate problems, Gross substitutes and complements: a simple generalization, The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems, Random paths to \(P\)-stability in the roommate problem, Deferred acceptance algorithms: history, theory, practice, and open questions, Moral hazard and stability, A new solution concept for the roommate problem: \(\mathcal{Q}\)-stable matchings, The Stable Roommates Problem with Short Lists, The Stable Roommates Problem with Choice Functions