本篇論文探討在二分圖中尋找最大匹配的問題。以兩種不同的運算模式一單通道廣播
通訊模式與高維立方體網路模式一為基礎，我們分別提出不同的平行演算法來解決此
一問題。在單通道廣播通訊模式上執行的平行演算法，如果廣播衝突可在定時中解決
，則利用n 個處理器需費時O（ｎ^1.5）；如果處理廣播衝突需要O（log n） 的時間
，則僅需使用n／log n個處理器而需時O（ｎ^1.5 log n） ，在高維立方體網路模式
執行演算法需時O（ｎ^1.5 log n）， 而藉著減少使用的處理器個數卻保持著相同的
時間複雜度的技巧，所需使用的處理器個數只為n／log n。為了在高維立方體網路模
式上解決最大匹配的問題，我們亦提出兩種平行搜尋演算法，一作廣度搜尋，另一作
深度搜尋。這兩種平行搜尋演算法均使用n／log n個處理器且費時O（n logn n）。
|