単純な無向グラフ G(V, E) がある場合、グラフの直径を O((|V|+|E|) * lg |V|) 実行時間で求めるにはどうすればよいでしょうか?
1 に答える
2
重み付けされていない無向グラフの最もよく知られているアルゴリズムは、Õ(n^ω) を取ると思います。ここで、n = |V| です。ω < 2.376 は高速行列乗算の指数です。また、O((|V|+|E|) * lg |V|) は Õ(n^2) を返します。これは、最もよく知られているアルゴリズムよりも優れています。簡単な調査と参照については、 http://arxiv.org/abs/1011.6181の紹介セクションを参照してください。
于 2013-03-25T01:05:43.610 に答える