BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-95-1544
       ENTRY:: February 14, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On Diameter Verification and Boolean Matrix Multiplication.
        TYPE:: Technical Report
      AUTHOR:: Basch, Julien
      AUTHOR:: Khanna, Sanjeev
      AUTHOR:: Motwani, Rajeev
        DATE:: February 1995
       PAGES:: 4
    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.
       NOTES:: [Adminitrivia V1/Prg/19950214]
         END:: STAN//CS-TR-95-1544