最有名的传递闭包算法图 [英] best known transitive closure algorithm for graph

问题描述

在运行时而言，什么是最有名的传递闭包的算法有向图？

In terms of runtime, what is the best known transitive closure algorithm for directed graphs?

我目前使用的沃肖尔的算法，但其为O（n ^ 3）。虽然，由于图形重新presentation我的实现确实稍好一些（而不是检查所有边缘，只检查全力以赴去边）。有没有传递闭包的算法比这更好的？具体而言，有什么专门针对共享内存多线程体系结构？

I am currently using Warshall's algorithm but its O(n^3). Although, due to the graph representation my implementation does slightly better (instead of checking all edges, it only checks all out going edges). Is there any transitive closure algorithm which is better than this? In particular, is there anything specifically for shared memory multi-threaded architectures?

在此先感谢。

Raghava。

推荐答案

本文探讨了各种传递闭包算法的性能：

This paper discusses the performance of various transitive closure algorithms:

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

从纸张的一个有趣的想法，是为了避免重复计算，整个封闭的曲线变化。

One interesting idea from the paper is to avoid recomputing the entire closure as the graph changes.

也有此页由艾司科Nuutila，其中列出了几​​个较新的算法：

There is also this page by Esko Nuutila, which lists a couple of more recent algorithms:

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

他的博士论文可能是最好的地方开始：

His PhD thesis listed on that page may be the best place to start:

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

从该网页：

该实验还表明，与重presentation区间   和新的算法，传递闭包可以计算   通常在时间线性于输入图形的大小。

The experiments also indicate that with the interval representation and the new algorithms, the transitive closure can be computed typically in time linear to the size of the input graph.

这篇关于最有名的传递闭包算法图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！