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