4
$\begingroup$

Is there any algorithm that decides whether a given directed acyclic graph is transitive or not, in time-complexity asymptotically better than boolean matrix multiplication?

| cite | |
$\endgroup$
  • $\begingroup$ By virgi's answer to your other question it's probably worths to merge this with the previous one. $\endgroup$ – Saeed Mar 13 '14 at 12:39