The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments

DOI10.1137/0217048zbMath0667.05002MaRDI QIDQ3819073

Dan Gusfield

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

zbMATH Keywords

complexitymatching algorithmmarriage problemstable roommate problem

Mathematics Subject Classification ID

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