On computing the diameter of real-world undirected graphs

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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2013, Graph Algorithms and Applications: in Honor of Professor Giorgio Ausiello, 514, pp.84-95. 〈10.1016/j.tcs.2012.09.018〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00936304
Contributeur : Michel Habib <>
Soumis le : vendredi 24 janvier 2014 - 18:42:53
Dernière modification le : jeudi 15 novembre 2018 - 20:27:23

Identifiants

Collections

Citation

Pilu Crescenzi, Roberto Grossi, Michel Habib, Leonardo Lanzi, Andrea Marino. On computing the diameter of real-world undirected graphs. Theoretical Computer Science, Elsevier, 2013, Graph Algorithms and Applications: in Honor of Professor Giorgio Ausiello, 514, pp.84-95. 〈10.1016/j.tcs.2012.09.018〉. 〈hal-00936304〉

Partager

Métriques

Consultations de la notice

283