The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Three Fast Algorithms for Four Problems in Stable Marriage
Abstract
The stable marriage problem is a well-known problem of matching n men to n women to achieve a certain type of “stability;” the $O(n^2 )$ time Gale-Shapley [GS] algorithm for finding two particular, but extreme, stable marriages (out of a possibly exponential number of stable marriages) is also well known. In this paper we consider four problems concerned with finding information about the set of all stable marriages, and with finding stable marriages other than those obtained by the Gale-Shapley algorithm. In particular, we give an $O(n^2 )$ time algorithm which, for any problem instance of n men and n women, finds every man–woman pair that is contained in at least one stable marriage; we show that the same algorithm finds all the “rotations” for the problem instance in $O(n^2 )$ time; we give an $O(n^2 + n|S|)$ time and $O(n^2 )$ space bounded algorithm (which is time and space optimal) to enumerate all stable marriages, where S is the set of them; and we give an $O(n^2 )$ time algorithm to find the minimum regret stable marriage (the best marriage, as measured by the person who is worst off in it). We believe the previous best time bounds for these problems are respectively $O(n^4 )$ (from a related problem in [K]), $O(n^3 )$ [ILG], $O(n^3 |S|)$ [K] and $O(n^4)$ [K]. The basic idea leading to the improved running times is to exploit theorems about the structure of stable marriages in order to avoid back-up and duplicated work inherent in earlier algorithms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
College Admissions and the Stability of Marriage
Gale, D., & Shapley, L. S. (1962) · The American Mathematical Monthly · doi:10.1080/00029890.1962.11989827 · Cited by 5,985
Cited by
Algorithmics of Matching Under Preferences
Manlove, D. F. (2013) · Series on Theoretical Computer Science · doi:10.1142/8591 · Cited by 515
Hard variants of stable marriage
Manlove, D. F., Irving, R. W., Iwama, K., Miyazaki, S., & Morita, Y. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00206-7 · Cited by 311
An efficient algorithm for the “optimal” stable marriage
Irving, R. W., Leather, P., & Gusfield, D. (1987) · Journal of the ACM · doi:10.1145/28869.28871 · Cited by 258
Self-citation
Metadata
- Authors
- Gusfield, D.
- Venue
- SIAM Journal on Computing
- Published
- 1987-02
- Volume
- 16
- Issue
- 1
- Pages
- 111-128
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2108186088
- Cited by
- 184
- References
- 1
- FWCI
- 12.52
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Three Fast Algorithms for Four Problems in Stable Marriage. https://app.cochat.ai/papers/10.1137/0216010
- The paper
- Gusfield, D. (1987). Three Fast Algorithms for Four Problems in Stable Marriage. SIAM Journal on Computing. https://doi.org/10.1137/0216010
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.