The diameter radius and node eccentricities of a graph are fundamental topological parameters that have many important practical applications in real world networks.For a-multiplicative B-additive approximations with expected “O ~(m^?)” time, there is a natural tradeoff between “a” and “?” Cairo et al proved lower bounds under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo et al, and upper bounds for undirected graphs. This project investigates the various techniques employed in relavant literature to generalize the results in Cairo et al to obtain new bounds for approximating extremal distances in directed graphs.

“I am intrigued by the elegance of combinatorial and algebraic algorithms, and I would like to investigate interesting open problems in the field.”