Name
Abstract | ||
|---|---|---|
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 Õ (n2 + m√n) time an estimate D for the diameter D in directed graphs with nonnegative edge weights, such that [EQUATION], 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 Õ (m√n). Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no O (n2-ε) 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 Õ (m3/2) time, and one running in Õ (mn2/3). 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 Õ (mn1-ε) time algorithm achieves an additive nε-approximation; no better results are known. We show that for any ε > 0, getting an additive nε-approximation algorithm for the diameter running in O (n2-ε) time for any δ > 2ε would falsify the Strong Exponential Time Hypothesis. Thus the simple algorithm is probably essentially tight for sparse graphs, and moreover, obtaining a subquadratic time additive c-approximation for any constant c is unlikely. 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 Õ (m√n) time, one can compute for each v ε V in an undirected graph, an estimate e(v) for the eccentricity ε (v) such that max{R, 2/3 · ε(v)} ≤ e (v) ≤ min {D, 3/2 · ε(v)} where R = minv ε (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 3/5 · ε (v) ≤ ε' (v) ≤ ε (v). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.5555/2634074.2634152 | SODA |
Keywords | Field | DocType |
algorithms,design,nonnumerical algorithms and problems,graph algorithms,approximation,theory | Discrete mathematics,Approximation algorithm,Combinatorics,Vertex (geometry),Directed graph,Distance,SIMPLE algorithm,Las Vegas algorithm,Mathematics,Exponential time hypothesis,Computation | Conference |
ISBN | Citations | PageRank |
978-1-61197-338-9 | 4 | 0.41 |
References | Authors | |
31 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shiri Chechik | 1 | 208 | 24.11 |
| Daniel Larkin | 2 | 38 | 4.43 |
| Liam Roditty | 3 | 919 | 52.14 |
| Grant Schoenebeck | 4 | 509 | 39.48 |
| Robert Endre Tarjan | 5 | 25160 | 6384.61 |
| Virginia Vassilevska Williams | 6 | 1066 | 60.36 |