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.