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.68069MaRDI 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
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, Random stable matchings, Popularity, Mixed Matchings, and Self-Duality, Two-Sided Matching Models, Popular Matchings in Complete Graphs, Hardness results for stable exchange problems, Planar Matchings for Weighted Straight Skeletons, Planar Matchings for Weighted Straight Skeletons, Hardness results for stable exchange problems, Review of the theory of stable matchings and contract systems, On stable flows and preflows, Stable and meta-stable contract networks, On the set of stable matchings in a bipartite graph, A note on roommate problems with a limited number of rooms, Weak stability against robust deviations and the bargaining set in the roommate problem, 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, The stable roommates problem with short lists, The existence of a unique core partition in coalition formation games, 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, Compromises and rewards: stable and non-manipulable probabilistic matching, The roommate problem with externalities, A bargaining set for roommate problems, A local interaction dynamic for the matching problem, Subjective homophily and the fixtures problem, One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences, Exchange-stability in roommate problems, Matching with partners and projects, Competitive equilibrium and singleton cores in generalized matching problems, The core of roommate problems: size and rank-fairness within matched pairs, 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, Popular matchings in complete graphs, Stability against robust deviations in the roommate problem, The Stable Roommates Problem with Short Lists, Small random instances of the stable roommates problem, The Stable Roommates Problem with Choice Functions