0
$\begingroup$

Show that if the transitive closure can be computed in T(|V |) time then BMM can be solved in O(T(3n)) time. I didn't understand the proof in the context of building edges. I added the proof

enter image description here

i tried to write an example

Michael P. Kim, Editted by: Bill Kuszmaul people.csail.mit.edu/virgi/6.890/lecture3.pdf

Thanks

$\endgroup$
  • $\begingroup$ What exactly you did not understand? $\endgroup$ – dkaeae Jan 10 at 16:42
  • 1
    $\begingroup$ Also, the proof seems to have been taken from some paper or similar. Please give the original author credit for their work. $\endgroup$ – dkaeae Jan 10 at 16:44
  • $\begingroup$ Scribe: Michael P. Kim, Editted by: Bill Kuszmaul people.csail.mit.edu/virgi/6.890/lecture3.pdf $\endgroup$ – Kate Jan 10 at 17:15
  • $\begingroup$ I wrote an example, now how to proceed after I have duplicated the matrices and created a graph? what is the next step? $\endgroup$ – Kate Jan 10 at 20:10
  • $\begingroup$ You compute which nodes on the right are reachable from which nodes on the left. This is transitive closure, and also the product of the two matrices. $\endgroup$ – Yuval Filmus Jan 11 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.