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.

Definition Forward Eccentricity of u: in how many hops u can reach any node? eccF (u)=
maxv∈ V d (u, v) Backward Eccentricity of u: in how many hops u can be reached starting
from any node? eccB (u)= maxv∈ V d (v, u) Diameter: maximum eccF or eccB v12 v11 v2 v1
v3 v8 v10 v5 v9 v6 v4 v7 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 eccF v1 0 2 1 3 1 3 2 3 2 4 1
2 4 v2 1 0 2 1 2 3 2 3 3 4 2 3 4 v3 2 1 0 2 3 2 1 2 4 3 3 4 4 v4 1 3 2 0 2 2 1 2 3 3 2 3 3 v5 3 2
1 2 0 3 2 2 1 3 4 5 5 v6 2 4 3 1 3 0 2 3 4 4 3 4 4 v7 3 4 3 2 2 1 0 1 3 2 4 5 5 v8 4 3 2 3 1 4 3 0 …