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.
If you would like to contact us about our work, please scroll down to the people section and click on one of the group leads' people pages, where you can reach out to them directly.