An algorithm for transitive closure is described with expected time O(n + m^ * ) where n is the number of nodes and m^ * is the expected number of edges in the transitive closure. Keywords transitive closure average time random access machines
No takes yet. Share an insight, caveat, or question.
C. P. Schnorr (1978) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: