• graph
• eccentricity
• diameter
• approximation
• algorithm
• radius

In this thesis, we consider the problem of computing approximations of extremal distances in undirected graphs, namely the diameter, the radius and the eccentricity of every vertex. This is a basic problem in computational graph theory: a number of recent results attracted the interest of researchers. We present some of the algorithmic techniques recently discovered to address this problem and the conditional lower bounds on its complexity, with particular focus on the relation with combinatorial and graph-theoretic aspects.

This thesis includes some results obtained by the author in collaboration with professor Roberto Grossi (thesis advisor, University of Pisa) and professor Romeo Rizzi (University of Verona), including new algorithms, conditional impossibility results, and combinatorial insights that improve our understanding of the problem. Our original contributions resulted in a paper which will be presented at the conference ACM--SIAM Symposium on Discrete Algorithms (SODA) in January 2016.