Three Fast Algorithms for Four Problems in Stable Marriage
From MaRDI portal
Publication:3774944
DOI10.1137/0216010zbMath0635.68036OpenAlexW2108186088MaRDI QIDQ3774944
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/e2f790f37626b390d62b69f70e6e9afca8ecd0cf
matchingstable marriage\(\alpha _ 0\)-product of automatasubautomatacombinational algorithm. homomorphisms of automata
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
The structure of stable marriage with indifference ⋮ Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings ⋮ Two-sided matching markets with strongly correlated preferences ⋮ Blockers and antiblockers of stable matchings ⋮ Constrained stable marriage with free edges or few blocking pairs ⋮ Unnamed Item ⋮ Stable matching with special preference patterns ⋮ Descending the stable matching lattice: how many strategic agents are required to turn pessimality to optimality? ⋮ Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings ⋮ Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case ⋮ Subquadratic algorithms for succinct stable matching ⋮ Solving stable matching problems using answer set programming ⋮ On the set of stable matchings in a bipartite graph ⋮ Stable allocations and partially ordered sets ⋮ Multi-agent reinforcement learning for decentralized stable matching ⋮ The complexity of approximately counting stable matchings ⋮ The necessary and sufficient condition for the worst-case male optimal stable matching ⋮ Understanding the generalized median stable matchings ⋮ Parameterized complexity and local search approaches for the stable marriage problem with ties ⋮ On the invariance of male optimal stable matching ⋮ The stable marriage problem with restricted pairs. ⋮ Approximability results for stable marriage problems with ties. ⋮ A unified approach to finding good stable matchings in the hospitals/residents setting ⋮ The stable roommates problem with short lists ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ Local search approaches in stable matching problems ⋮ Stability, optimality and manipulation in matching problems with weighted preferences ⋮ Stable fractional matchings ⋮ Bribery and Control in Stable Marriage ⋮ Center Stable Matchings and Centers of Cover Graphs of Distributive Lattices ⋮ A new fixed point approach for stable networks and stable marriages ⋮ Sex-equal stable matchings: complexity and exact algorithms ⋮ Keeping partners together: Algorithmic results for the hospitals/residents problem with couples ⋮ From Marriages to Coalitions: A Soft CSP Approach ⋮ A stable marriage requires communication ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ The Generalized Median Stable Matchings: Finding Them Is Not That Easy ⋮ The stable marriage problem with master preference lists ⋮ Balanced stable marriage: how close is close enough? ⋮ Extracting maximal information about sets of minimum cuts ⋮ Finding All Stable Pairs and Solutions to the Many-to-Many Stable Matching Problem ⋮ Stable matching problems with exchange restrictions ⋮ Efficient algorithms and methods to solve dynamic MINs stability problem using stable matching with complete ties ⋮ The Stable Roommates Problem with Short Lists ⋮ The diameter of the stable marriage polytope: bounding from below ⋮ Coalitional permutation manipulations in the Gale-Shapley algorithm ⋮ On Vertices and Facets of Combinatorial 2-Level Polytopes ⋮ A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences ⋮ Polyhedral Aspects of Stable Marriage ⋮ Finding a minimum-regret many-to-many Stable Matching ⋮ Network flow and 2-satisfiability ⋮ A unifying approach to the structures of the stable matching problems ⋮ Hard variants of stable marriage.
This page was built for publication: Three Fast Algorithms for Four Problems in Stable Marriage
