Report Number: CS-TR-95-1544
Institution: Stanford University, Department of Computer Science
Title: On Diameter Verification and Boolean Matrix Multiplication.
Author: Basch, Julien
Author: Khanna, Sanjeev
Author: Motwani, Rajeev
Date: February 1995
Abstract: We present a practical algorithm that verifies whether a graph has diameter 2 in time O(n^{3} / log^{2} n}). A slight adaptation of this algorithm yields a boolean matrix multiplication algorithm which runs in the same time bound; thereby allowing us to compute transitive closure and verification of the diameter of a graph for any constant $d$ in O(n^{3} / log^{2} n}) time.
http://i.stanford.edu/pub/cstr/reports/cs/tr/95/1544/CS-TR-95-1544.pdf