Diameter Verification and Boolean Matrix Multiplication

摘要

We present a practical algorithm that verifies wheather a graph has diameter 2 intime O(n cubed over log squared n). A slight adaption 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 cubed over log squared n).