The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
From MaRDI portal
Publication:3819073
DOI10.1137/0217048zbMath0667.05002OpenAlexW2047631336MaRDI QIDQ3819073
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217048
Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)
Related Items (16)
How to split the costs and charge the travellers sharing a ride? Aligning system's optimum with users' equilibrium ⋮ The cycle roommates problem: a hard case of kidney exchange ⋮ The stable fixtures problem -- a many-to-many extension of stable roommates ⋮ Recognizing when a preference system is close to admitting a master list ⋮ Recognizing when a preference system is close to admitting a master list ⋮ The complexity of approximately counting stable roommate assignments ⋮ A maximum stable matching for the roommates problem ⋮ Subjective homophily and the fixtures problem ⋮ Two-Sided Matching Models ⋮ A bounded approximation for the minimum cost 2-sat problem ⋮ A new fixed point approach for stable networks and stable marriages ⋮ Rotations in the stable \(b\)-matching problem ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ Compact linear programs for 2SAT ⋮ Network flow and 2-satisfiability ⋮ A unifying approach to the structures of the stable matching problems
This page was built for publication: The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
