最小カット問題に対する擬似決定論的アルゴリズム

本論文は、グローバル最小カットやs-tカットを含む最小カット問題に対する効率的な擬似決定論的アルゴリズムを提案しています。その重要性は、グローバル最小カットに対する既存の決定論的アルゴリズムと比較して改善された実行時間と、効率的な決定論的解法が存在しないモデルへの適用可能性にあります。これは、計算効率の向上と、最小カット解法のより広い適用範囲を示唆しています。

• •最小カット問題に対する効率的な擬似決定論的アルゴリズムを提示。
• •既存の決定論的アルゴリズムと比較して、グローバル最小カットの実行時間を改善。
• •効率的な決定論的アルゴリズムが知られていないモデル（逐次、ストリーミング、PRAM、カットクエリ）に適用可能。