A parallel algorithm to solve the stable marriage problem

DOI10.1007/BF02136029MaRDI QIDQ798000zbMATH OpenOpenAlexFDO

Authors Shian-Shyong Tseng, R. C. T. 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

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

Recommendations

• The average performance of a parallel stable mariage algorithm
• Worst-case choice for the stable marriage problem
• A sublinear parallel algorithm for stable matching
• scientific article; zbMATH DE number 1003296
• An efficient algorithm for the “stable roommates” problem

Cites work

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

Cited in

(12)

• On the decomposability of the stable marriage problem
• A neural network approach to solve the stable matching problem
• The average performance of a parallel stable mariage algorithm
• High Performance Computing - HiPC 2003
• Distributed Weighted Stable Marriage Problem
• Efficient algorithms and methods to solve dynamic MINs stability problem using stable matching with complete ties
• Almost stable matchings by truncating the Gale-Shapley algorithm
• The necessary and sufficient condition for the worst-case male optimal stable matching
• On the invariance of male optimal stable matching
• Worst-case choice for the stable marriage problem
• On stable marriages and greedy matchings
• Stable matching with special preference patterns

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

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