SIAM Journal on Computing · 1994 · 78 citations · 24 references
Natural SciencesComputer ScienceMathematicsCombinatoricsComputer NetworksProperty DivisionAssignment ProblemsMatching TheoryGraph MatchingMarriage ProblemMatching AlgorithmsMatching ProblemsParallel ReductionParallel Reduction AlgorithmsSimple AlgorithmStable Roommates Problem
It is shown that Stable Matching problems are the same as problems about stable configurations of X-networks. Consequences include easy proofs of old theorems, a new simple algorithm for finding a stable matching, an understanding of the difference between Stable Marriage and Stable Roommates, NP-completeness of Three-party Stable Marriage, CC-completeness of several Stable Matching problems, and a fast parallel reduction from the Stable Marriage problem to the Assignment problem.
24
Introduction to automata theory, languages, and computation
Computer Languages · 1980 · 6.9K citations
The Complexity of Enumeration and Reliability Problems
Leslie G. Valiant · SIAM Journal on Computing · 1979 · 2.1K citations