A necessary and sufficient condition for the existence of a complete stable matching
From MaRDI portal
Publication:3201772
DOI10.1016/0196-6774(91)90028-WzbMath0715.68069OpenAlexW2029388009MaRDI QIDQ3201772
Publication date: 1991
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(91)90028-w
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Parallel algorithms in computer science (68W10)
Related Items (65)
A new solution concept for the roommate problem: \(\mathcal{Q}\)-stable matchings ⋮ On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm ⋮ Competitive equilibrium and singleton cores in generalized matching problems ⋮ A local interaction dynamic for the matching problem ⋮ Popular matchings in complete graphs ⋮ Analysis of stochastic matching markets ⋮ Stability against robust deviations in the roommate problem ⋮ Review of the theory of stable matchings and contract systems ⋮ On stable flows and preflows ⋮ Stochastic stability for roommate markets ⋮ Stable and meta-stable contract networks ⋮ On the set of stable matchings in a bipartite graph ⋮ The Stable Roommates Problem with Choice Functions ⋮ The core of roommate problems: size and rank-fairness within matched pairs ⋮ On a lemma of Scarf. ⋮ A note on roommate problems with a limited number of rooms ⋮ Weak stability against robust deviations and the bargaining set in the roommate problem ⋮ Core of coalition formation games and fixed-point methods ⋮ ``Almost stable matchings in the roommates problem with bounded preference lists ⋮ Absorbing sets in roommate problems ⋮ The integral stable allocation problem on graphs ⋮ The roommates problem revisited ⋮ The stable roommates problem with choice functions ⋮ Faster algorithms for stable allocation problems ⋮ An algorithm for a super-stable roommates problem ⋮ A maximum stable matching for the roommates problem ⋮ Hardness results for stable exchange problems ⋮ Subjective homophily and the fixtures problem ⋮ One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences ⋮ Gross substitutes and complements: a simple generalization ⋮ Dominance invariant one-to-one matching problems ⋮ When do stable roommate matchings exist? A review ⋮ The stable roommates problem with short lists ⋮ The existence of a unique core partition in coalition formation games ⋮ Small random instances of the stable roommates problem ⋮ Two-Sided Matching Models ⋮ Large roommate problem with non-transferable random utility ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Fractional solutions for capacitated NTU-games, with applications to stable matchings ⋮ Compromises and rewards: stable and non-manipulable probabilistic matching ⋮ Rotations in the stable \(b\)-matching problem ⋮ 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 ⋮ Unique stability in simple coalition formation games ⋮ A model of partnership formation ⋮ Random paths to stability in the roommate problem ⋮ Impossibilities for roommate problems ⋮ Smith and Rawls share a room: stability and medians ⋮ The roommate problem with externalities ⋮ Exchange-stability in roommate problems ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ Representing roommates' preferences with symmetric utilities ⋮ A bargaining set for roommate problems ⋮ Moral hazard and stability ⋮ Planar Matchings for Weighted Straight Skeletons ⋮ Planar Matchings for Weighted Straight Skeletons ⋮ Hardness results for stable exchange problems ⋮ A generalization of the stable matching problem ⋮ Random stable matchings ⋮ The Stable Roommates Problem with Short Lists ⋮ Popular Matchings in Complete Graphs ⋮ Popularity, Mixed Matchings, and Self-Duality ⋮ Matching with partners and projects ⋮ On the existence of stable roommate matchings
This page was built for publication: A necessary and sufficient condition for the existence of a complete stable matching
