Toward Tight Approximation Bounds for Graph Diameter and Eccentricities

Among the most important graph parameters is the diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the diameter exactly. Thus, much...