一千萬個為什麽

搜索

PRAM上的哪種算法以最小的時間復雜度計算圖的連通分量?


在我發現的PRAM上計算無向圖的連通分量的最快方法是1993年論文中的O(log n loglog n)在EREW PRAM上查找O(log n loglog n)時間內的連通組件,由K. Chong和T. Lam撰寫。是否存在時間復雜度較小的算法?

最佳答案

正如傑夫建議的那樣,我將評論移至答案部分:

在CRCW PRAM上,實現$ O(\ log n)$時間相當容易(參見J.訴Leeuwen,TCS手冊,第17章)。

在EREW PRAM上,Chong,Han和Lam(JACM,Vol 48(2),2001)在EREW PRAM上為MST提供了$ O(\ log n)$算法。這也應該解決CC問題。或者,使用Reingold的logspace算法進行無向連接和標準模擬方法。

轉載註明原文: PRAM上的哪種算法以最小的時間復雜度計算圖的連通分量?

猜你喜歡