接続成分を見つけるための並列アルゴリズムの比較

本論文では、接続成分を見つけるためのいくつかの並列アルゴリズムの実用的側面の比較と、これらのアルゴリズムに対する最適化を示します。比較されるアルゴリズムは、Shiloach-Vishkin 22 と Awerbuch-Shiloach 2 による二つの類似のアルゴリズム、Reif 21 と Phillips 20 に基づくランダム化された収縮アルゴリズム、およびハイブリッドアルゴリズム 11 です。前者の二つについては性能を大幅に改善するための改良が行われていますが、漸近的な複雑性は向上していません。このハイブリッドアルゴリズムは他のアルゴリズムの特徴を組み合わせており、テストされた中では一般的に最も高速です。タイミングは、Connection Machine 2 と Cray Y-MP/C90 で実行したNESL 4 コードを使用して行われました。