performance - 如何获得图形直径的运行时间？

Question

如果您有一个简单的无向图 G(V, E)，如何在 O((|V|+|E|) * lg |V|) 运行时间中找到图的直径？

Answer 1

我认为最知名的未加权无向图算法采用 Õ(n^ω)，其中 n = |V| ω < 2.376 是快速矩阵乘法的指数。O((|V|+|E|) * lg |V|) 会给我们 Õ(n^2)，这比最知名的算法要好。查看http://arxiv.org/abs/1011.6181的介绍部分以获得简要调查和参考。