On Computing the Diameter of Real-World Directed (Weighted) Graphs
On Computing the Diameter of Real-World Directed (Weighted) Graphs
复制标题
关于计算现实世界有向（加权）图的直径
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Andrea Marino
中科院分区：
文献类型：
--
作者：
P. Crescenzi;R. Grossi;L. Lanzi;Andrea Marino
在本文中，我们提出了一个新的算法计算直径的有向赋权图。即使在最坏的情况下，该算法的复杂度为O（nm），其中n是节点数，m是图的边数，我们的实验表明，在实践中，我们的方法在O（m）时间内工作。此外，我们展示了如何将我们的算法扩展到有向加权图的情况下，即使在这种情况下，我们提出了一些初步的非常积极的实验结果。
In this paper we propose a new algorithm for computing the diameter of directed unweighted graphs. Even though, in the worst case, this algorithm has complexity O(nm), where n is the number of nodes and m is the number of edges of the graph, we experimentally show that in practice our method works in O(m) time. Moreover, we show how to extend our algorithm to the case of directed weighted graphs and, even in this case, we present some preliminary very positive experimental results.