On efficiently computing the product of two binary relations

Abstract

We precisely analyse ideas of M. A. Kronrod for the efficient composition of binary relations on finite domains. It shows that the “Four Russians” algorithm for Boolean matrix multiplication behaves no different in average and worst cases, which therefore makes it less preferable for use than is often claimed.