We propose a new algorithm for the classical problem of computing the diameter of undirected unweighted graphs, namely, the maximum distance among all the pairs of nodes, where the distance of a pair of nodes is the number of edges contained in the shortest path connecting these two nodes. Although its worst-case complexity is O(nm) time, where n is the number of nodes and m is the number of edges of the graph, we experimentally show that our algorithm works in O(m) time in practice, requiring few breadth-first searches to complete its task on almost 200 real-world graphs.
On computing the diameter of real-world undirected graphs / P. Crescenzi; R. Grossi; M. Habib; L. Lanzi; A. Marino. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - ELETTRONICO. - 514:(2013), pp. 84-95. [10.1016/j.tcs.2012.09.018]
On computing the diameter of real-world undirected graphs
CRESCENZI, PIERLUIGI;GROSSI, ROBERTO;LANZI, LEONARDO;MARINO, ANDREA
2013
Abstract
We propose a new algorithm for the classical problem of computing the diameter of undirected unweighted graphs, namely, the maximum distance among all the pairs of nodes, where the distance of a pair of nodes is the number of edges contained in the shortest path connecting these two nodes. Although its worst-case complexity is O(nm) time, where n is the number of nodes and m is the number of edges of the graph, we experimentally show that our algorithm works in O(m) time in practice, requiring few breadth-first searches to complete its task on almost 200 real-world graphs.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
