对于有向图,最着名的传递闭包算法是什么？

Question

在运行时方面,有向图的最着名的传递闭包算法是什么？

我目前正在使用Warshall的算法但它的O(n ^ 3).虽然,由于图形表示我的实现稍微好一点(而不是检查所有边缘,它只检查所有前进边缘).有没有比这更好的传递闭包算法？特别是,有没有专门用于共享内存多线程架构的东西？

Answer 1

本文讨论了各种传递闭包算法的性能:

http://www.vldb.org/conf/1988/P382.PDF

本文的一个有趣的想法是避免在图形发生变化时重新计算整个闭包.

Esko Nuutila也有这个页面,它列出了几个最近的算法:

http://www.cs.hut.fi/~enu/tc.html

他在该页面上列出的博士论文可能是最好的起点:

http://www.cs.hut.fi/~enu/thesis.html

从该页面:

实验还表明,利用区间表示和新算法,可以通常在与输入图的大小成线性的时间内计算传递闭包.

Answer 2

该算法设计手册有一些有用的信息.关键点:

• 传递闭包与矩阵乘法一样困难; 所以最着名的界限是Coppersmith-Winograd算法,该算法在O(n ^ 2.376)中运行,但实际上使用矩阵乘法算法可能并不值得.
• 对于启发式加速,首先计算强连通分量.