Student or educator? Sign up with your school email and get 6 months of Pro free.
Cited by 184

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

Gusfield, Dan · 1987 · SIAM Journal on Computing

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1137/0216010

Cites

1 of 1 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 1 references

Cited by

See all 184

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.