language-agnostic - 计算图的传递闭包需要渐近运行时间？

Question

图的传递闭包在此处定义，例如：http: //mathworld.wolfram.com/TransitiveClosure.html

在 O(n^3) 中很容易实现，其中 n 是顶点数。我想知道它是否可以在 O(n^2) 时间内完成。

score 3 · Accepted Answer

没有。我不认为它有一个 O(n ² ) 算法。我希望如果存在这样的算法，您也可以解决 O(n ² ) 中的所有对最短路径问题，但事实并非如此。我能想到的渐近最快的算法是 Dijkstra 的最短路径算法的一个实现，它带有一个斐波那契堆（O( n ² log n ) 在不是很密集的图中）。

score 1 · Accepted Answer

1

唔。我找到了一种算法，可以在 O(n^2) 预期运行时间内计算传递闭包。

于 2009-04-01T00:08:49.530 回答

score 1 · Accepted Answer

鉴于此：

你能想出一个 O(kn^2 + m) 传递闭包/归约算法，其中 k 是传递闭包/归约中缺失/额外边的数量吗？

仍然被那些比我们想得更多的人认为是一个悬而未决的问题，我会说“我不知道”。

（但如果你解决了它并想要获得博士学位，我知道那个算法。）

3 回答 3