Abstract
在這篇論文□，我們提出幾個在單一通道的廣播通訊模式下設計的平行演算法。它們解決了幾個圖形的問題，包括計算一個有向圖的遞迴閉包（transitive cloure ）找出一個有向圖中所有頂點間的最短路徑長度、計算一個無週期有向圖中各頂點的支配者（dominator ），找出某個K 階圖（K-stage graph ）中的最短路徑（由起點到終點）長度和找出一個無向圖的最大獨立集（maximal independent set ）。我們所設計的演算法都在兩種廣播通訊解衝模式下做分析。第一種是一理想的模式，其假設一個廣播衝突（broadcast conflict）可以在常數的時間內解決。第二種是一較實際的模式，其利用Capetanakis 氏所提出的樹演算法（Tree's Algorithm）來解決一個廣播衝突；如果在廣播通訊系統中有n 個處理機，則在最壞的情況下此演算法所花費的時間為0 (logn)。在這兩種模式下，前三個演算法都利用了n 個處理機並花了0 (n2)的時間，因為它們皆為忽略衝突（conflictignoring）的演算法。至於最後兩個演算法，它們在第一種模式下使用了n 個處理機花了o (n) 的時間達到了最佳效率（optimal speedup ），並且可利用少於n/logn個處理機依然在第二種模式下達到最佳效率。此外，前兩個演算法還可飲處理機依某種固定順序輪流廣播而變成免於衝突（conflictfree）的演算法。