Lower Bounds for the Stable Marriage Problem and Its Variants
From MaRDI portal
DOI10.1137/0219004zbMATH Open0696.68067OpenAlexW2155827882MaRDI QIDQ3474282FDOQ3474282
Authors: Cheng Ng, Daniel S. Hirschberg 
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://escholarship.org/uc/item/82n213qg
Recommendations
Analysis of algorithms and problem complexity (68Q25) Operations research and management science (90B99)
Cited In (19)
- An efficient algorithm for batch stability testing
- Comment on worst-case choice for the stable marriage problem
- Stable marriage and indifference
- Subquadratic algorithms for succinct stable matching
- The complexity of the certification of properties of stable marriage
- Two algorithms for the student-project allocation problem
- Lazy Gale-Shapley for many-to-one matching with partial information
- The stable fixtures problem -- a many-to-many extension of stable roommates
- On the stable \(b\)-matching problem in multigraphs
- Parametric stable marriage and minimum cuts
- A formal theory for the complexity class associated with the stable marriage problem
- A stable marriage requires communication
- Worst-case choice for the stable marriage problem
- Three Fast Algorithms for Four Problems in Stable Marriage
- Of Stable Marriages and Graphs, and Strategy and Polytopes
- The diameter of the stable marriage polytope: bounding from below
- Efficient algorithms for generalized stable marriage and roommates problems
- The stable marriage problem with restricted pairs.
- Stable marriage with covering constraints -- a complete computational trichotomy
This page was built for publication: Lower Bounds for the Stable Marriage Problem and Its Variants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3474282)
