A parallel algorithm to solve the stable marriage problem |
| |
| Authors: | S S Tseng R C T Lee |
| |
| Institution: | (1) Institute of Computer Engineering, College of Engineering, National Chiao Tung University, Hsinchu, Taiwan, Republic of China;(2) Institute of Computer and Decision Sciences, National Tsing Hua University, Hsinchu, Taiwan, Republic of China |
| |
| Abstract: | In this paper a parallel algorithm to solve the stable marriage problem is given. The worst case performance of this algorithm is stated. A theoretical analysis shows that the probability of the occurrence of this worst case is extremely small. For instance, if there are sixteen men and sixteen women involved, then the probability that the worst case occurs is only 10–45. Possible future research is also discussed in this paper. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
