A parallel algorithm to solve the stable marriage problem

DOI10.1007/BF02136029zbMath0546.68048OpenAlexW2052785830MaRDI QIDQ798000

Shian-Shyong Tseng, Richard Chia-Tung Lee

Publication date: 1984

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02136029

zbMATH Keywords

parallel algorithmstable marriage problemworst case performance

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Ordered sets (06A99) Discrete mathematics in relation to computer science (68R99)

Related Items (8)

The average performance of a parallel stable mariage algorithm ⋮ Stable matching with special preference patterns ⋮ The necessary and sufficient condition for the worst-case male optimal stable matching ⋮ Almost stable matchings by truncating the Gale-Shapley algorithm ⋮ On the invariance of male optimal stable matching ⋮ Efficient algorithms and methods to solve dynamic MINs stability problem using stable matching with complete ties ⋮ A neural network approach to solve the stable matching problem ⋮ On the decomposability of the stable marriage problem

Cites Work

• Multidimensional divide-and-conquer
• Stable marriages by coroutines
• Stable marriage assignment for unequal sets
• An analysis of the stable marriage assignment algorithm
• College Admissions and the Stability of Marriage

This page was built for publication: A parallel algorithm to solve the stable marriage problem