グラフの推移的クロージャを計算するために必要な実行時間

Question

グラフの推移的閉包は、e。 g。ここで、http://mathworld.wolfram.com/TransitiveClosure.html

O（n^3）（nは頂点の数）では簡単に可能です。私はそれが時間O（n^2）で完了できるかどうか疑問に思っていた。

Answer 1

いいえ。私は、O（n ）アルゴリズムがあるとは思わない。私はそのようなアルゴリズムが存在すれば、O（n ）のすべてのペアの最短パス問題を解決することができますが、そうではありません。私が考えることができる漸進的に最速のアルゴリズムは、フィボナッチヒープを持つDijkstraの最短経路アルゴリズムの実装です（それほど高密度のグラフではありません）。

Answer 2

Hmm。私はO（n^2）EXPECTEDランタイムで推移的閉包を計算するアルゴリズムを発見しました。

Answer 3

このことを考える：

あなたはO（KN^2 + m）のkが推移 閉鎖で行方不明/余分なエッジの数で推移閉包/縮小 アルゴリズム、思い付くことができます/削減？

私はこれ以上のことを考えている人がまだ未解決の質問だと思うが、私は「わからない」と言っている。

（しかし、あなたはそれを解決し、博士号を取得したい場合は、私が知っているそのアルゴリズム。）がランダムに分布して