language-agnostic - グラフの推移閉包を計算するために必要な漸近実行時間?

Question

グラフの推移閉包は、たとえばここで定義されます: http://mathworld.wolfram.com/TransitiveClosure.html

O（n ^ 3）で簡単に可能です。ここで、nは頂点の数です。時間O(n^2)でできるかどうか疑問に思っていました。

Answer 1

いいえ。^{O(n 2} ) アルゴリズムはないと思います。^{そのようなアルゴリズムが存在する場合、O(n 2} ) でもすべてのペア最短経路問題を解決できると思いますが、そうではありません。私が考えることができる漸近的に最速のアルゴリズムは、フィボナッチヒープを使用したダイクストラの最短経路アルゴリズムの実装です (密度の低いグラフではO( n ² log n ))。

Answer 2

これを考えると：

O(kn^2 + m) 推移閉包/削減アルゴリズムを考え出すことはできますか? ここで、k は推移閉包/削減における欠落/余分なエッジの数です。

この種のことを私たちよりも多く考える人々にとっては、いまだに未解決の質問と見なされていますが、私は「わかりません」と言います.

(しかし、もしあなたがそれを解いて博士号を取得したいなら、私はそのアルゴリズムを知っています。)

Answer 3

うーん。O(n^2) EXPECTED ランタイムで推移閉包を計算するアルゴリズムを見つけました。