The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
From MaRDI portal
Publication:3819073
DOI10.1137/0217048zbMath0667.05002MaRDI 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
68Q25: Analysis of algorithms and problem complexity
06A06: Partial orders, general
05A05: Permutations, words, matrices
68R10: Graph theory (including graph drawing) in computer science
90C27: Combinatorial optimization
Related Items
Two-Sided Matching Models, 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 unifying approach to the structures of the stable matching problems, A maximum stable matching for the roommates problem, Rotations in the stable \(b\)-matching problem, Efficient algorithms for generalized stable marriage and roommates problems, A bounded approximation for the minimum cost 2-sat problem, A new fixed point approach for stable networks and stable marriages, Network flow and 2-satisfiability, How to split the costs and charge the travellers sharing a ride? Aligning system's optimum with users' equilibrium, Subjective homophily and the fixtures problem, Compact linear programs for 2SAT, The cycle roommates problem: a hard case of kidney exchange, The stable fixtures problem -- a many-to-many extension of stable roommates