The diameter is a fundamental graph parameter and its computation is necessary in many applications. The fastest known way to compute the diameter exactly is to solve the All-Pairs Shortest Paths (APSP) problem.

In the absence of fast algorithms, attempts were made to seek fast algorithms that approximate the diameter.
In a seminal result Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] designed an algorithm that computes in $\OTilde{n^2+m\sqrt n}$
time an estimate D* for the diameter *D* in directed graphs with nonnegative edge weights, such that ⌊⅔ · *D*⌋ – (*M* – 1) ≤
D*
≤ *D*, where *M* is the maximum edge weight in the graph. In recent work, Roditty and Vassilevska W. [STOC 13] gave a Las Vegas algorithm that has the same approximation guarantee but improves the (expected) runtime to
$\OTilde{m\sqrt n}$.
Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no
O(*n*^{2−∊})
time algorithm for sparse unweighted undirected graphs can achieve an approximation ratio better than
3/2.
Thus their algorithm is essentially tight for sparse unweighted graphs. For weighted graphs however, the approximation guarantee can be meaningless, as *M* can be arbitrarily large.

In this paper we exhibit two algorithms that achieve a genuine
3/2-approximation for the diameter, one running in
O(m^{3/2})
time, and one running in
O(mnn^{3/2})
time. Furthermore, our algorithms are *deterministic*, and thus we present the first deterministic (2 – *∊*)-approximation algorithm for the diameter that takes subquadratic time in sparse graphs.

In addition, we address the question of obtaining an *additive c*-approximation for the diameter, i.e. an estimate
D* such that *D – c ≤* D* ≤ *D*. An extremely simple
$\OTilde{m\sqrt n}$
time algorithm achieves an additive *n ^{∊}*-approximation; no better results are known. We show that for any

Finally, we consider the problem of computing the *eccentricities* of all
vertices in an undirected graph, i.e. the largest distance from each vertex. Roditty and Vassilevska W. [STOC 13] show that in
$\OTilde{m\sqrt n}$
time, one can compute for each *v* ∊ *V* in an undirected graph, an estimate ∊(*v*) for the eccentricity ∊(*v*) such that max {*R*,
2/3 · ∊(*v*)} ≤ ∊(*v*) ≤ min {*D*,
3/2 · ∊(*v*)} where *R* = min_{v} ∊(v) is the radius of the graph. Here we improve the approximation guarantee by showing that a variant of the same
algorithm can achieve estimates ∊*′*(*v*) with 5/3 · ∊(*v*) ≤ *∊′*(*v*) ≤ ∊(*v*).

[ back to Grant's homepage]