A parallel algorithm to solve the stable marriage problem

DOI10.1007/BF02136029zbMath0546.68048MaRDI 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 algorithm; stable marriage problem; worst case performance

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

06A99: Ordered sets

68R99: Discrete mathematics in relation to computer science

Related Items

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

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