Worst-case choice for the stable marriage problem

DOI10.1016/0020-0190(85)90104-8MaRDI QIDQ1063004zbMATH OpenOpenAlexFDO

Authors Deepak Kapur, Mukkai S. Krishnamoorthy

Publication date 1985

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(85)90104-8

zbMATH Keywords

parallel algorithmstable marriage problemworst-case choice

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Review text

We present a worst-case choice for the stable marriage problem which takes the maximum number of stages for \textit{D. Gale} and \textit{L. S. Shapely}'s algorithm [Amer. Math. Monthly 69, 9-15 (1962; Zbl 0109.244)]. We also analyze a coroutine solution recently suggested by \textit{L. Allison} [Inf. Process. Lett. 16, 61-65 (1983; Zbl 0513.68064)] as well as a parallel algorithm for this problem.

Recommendations

• A parallel algorithm to solve the stable marriage problem
• Lower Bounds for the Stable Marriage Problem and Its Variants
• An efficient algorithm for the “stable roommates” problem
• Comment on worst-case choice for the stable marriage problem
• A stable marriage requires communication

Cites work

• College Admissions and the Stability of Marriage
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3841211 (Why is no real title available?)
• Stable marriage assignment for unequal sets
• Stable marriages by coroutines

Cited in

(6)

• Comment on worst-case choice for the stable marriage problem
• The average performance of a parallel stable mariage algorithm
• A neural network approach to solve the stable matching problem
• scientific article; zbMATH DE number 6672022 (Why is no real title available?)
• A parallel algorithm to solve the stable marriage problem
• The necessary and sufficient condition for the worst-case male optimal stable matching

This page was built for publication: Worst-case choice for the stable marriage problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1063004)