Computing extremal and approximate distances in graphs having unit cost edges

Summary Using binary search and a Strassen-like matrix multiplication algorithm we obtain efficient algorithms for computing the diameter, the radius, and other distance-related quantities associated with undirected and directed graphs having unit cost (unweighted) edges. Similar methods are used to find approximate values for the distances between all pairs of vertices, and if the graph satisfies certain regularity conditions to find the exact distances.A preliminary version of this research was presented at the Sixteenth Annual Allerton Conference on Communication, Control, and Computing and appears in the Proceedings for that conference. This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under grant A4307 and by the Office of Naval Research under grant N00014-75-6-0752