2015 · 20 citations · 21 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationApproximation AlgorithmsGeometric ApproximationGraph AlgorithmsGraph TheoryNetwork DiameterRandomized Geometric AlgorithmsApproximate DiameterComputational Complexity Of Graph AlgorithmsDominating Set ApproximationDominating SetsEccentricityLower Bounds On DiameterUpper BoundsUpper Bounds On Diameter
We provide new bounds for the approximation of extremal distances (the diameter, the radius, and the eccentricities of all nodes) of an undirected graph with n nodes and m edges. First, we show under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi and Zane [JCSS01] that it is impossible to get a (3/2 – ∊)-approximation of the diameter or a (5/3 – ∊)-approximation of all the eccentricities in O(m2–δ) time for any ∊, δ > 0, even allowing for a constant additive term in the approximation. Second, we present an algorithmic scheme that gives a (2 – 1/2k)-approximation of the diameter and the radius and a (3 – 4/(2k + 1))-approximation of all eccentricities in expected time for any k ≥ 0. For k ≥ 2, this gives a family of previously unknown bounds, and approaches near-linear running time as k grows. Third, we observe a connection between the approximation of the diameter and the h-dominating sets, which are subsets of nodes at distance ≤ h from every other node. We give bounds for the size of these sets, related with the diameter.
21
Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
D. Aingworth, Chandra Chekuri, Piotr Indyk et al. · SIAM Journal on Computing · 1999 · 337 citations
New Bounds on the Complexity of the Shortest Path Problem
Michael L. Fredman · SIAM Journal on Computing · 1976 · 265 citations