An Exact Algorithm for Diameters of Large Real Directed Graphs
An Exact Algorithm for Diameters of Large Real Directed Graphs
复制标题
DOI：
10.1007/978-3-319-20086-6_5
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Takuya Akiba;Yoichi Iwata;Yuki Kawata
中科院分区：
文献类型：
--
作者：
Takuya Akiba;Yoichi Iwata;Yuki Kawata
提出了一种计算大型实数有向图直径的新算法。与最近的算法相比，所提出的算法是针对一般有向图设计的，也就是说，它不假设给定的图是无向或强连接的。在大型实数图上的实验结果表明，该算法比原始方法快了几个数量级，并揭示了大型实数有向图的确切直径，而只有下界是已知的。
We propose a new algorithm to compute the diameters of large real directed graphs. In contrast to recent algorithms, the proposed algorithm is designed for general directed graphs, i.e., it does not assume that given graphs are undirected or strongly connected. Experimental results on large real graphs show that the proposed algorithm is several orders of magnitude faster than the naive approach, and it reveals the exact diameters of large real directed graphs, for which only lower bounds have been known.