Lower Bounds for the Stable Marriage Problem and Its Variants

DOI10.1137/0219004zbMath0696.68067OpenAlexW2155827882MaRDI QIDQ3474282

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

zbMATH Keywords

analysis of algorithmslower boundsstable marriage problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Operations research and management science (90B99)

Related Items (10)

The complexity of the certification of properties of stable marriage ⋮ The stable fixtures problem -- a many-to-many extension of stable roommates ⋮ Subquadratic algorithms for succinct stable matching ⋮ Lazy Gale-Shapley for many-to-one matching with partial information ⋮ An efficient algorithm for batch stability testing ⋮ Two algorithms for the student-project allocation problem ⋮ On the stable \(b\)-matching problem in multigraphs ⋮ A stable marriage requires communication ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ Stable marriage and indifference

This page was built for publication: Lower Bounds for the Stable Marriage Problem and Its Variants