There is a family of approximation algorithms for computing the diameter of an undirected graph that give a time/accuracy trade-off and our goal is to extend these results to directed graphs.
Computing the diameter of a graph (the distance between the two most distant vertices) is one of the most fundamental problems in graph algorithms. It has been conjectured that there is no algorithm for the problem that runs substantially faster than cubic time. Given that cubic time is impractical for some applications, we consider the problem of finding faster approximation algorithms. For all k>1 there is an O(mn^(1/(k+1))) time algorithm (ignoring logarithmic factors) that gives a nearly 2-1/(2^k) multiplicative approximation for the diameter of an undirected, weighted graph (assuming the triangle inequality). This result only extends to directed graphs for extreme values of k. In this project we focus on intermediate values of k: we aim to understand the full trade-off between time and accuracy for computing the diameter of a directed graph.
