Parallel constructing of the shortest coverings of large Boolean matrices

Abstract

The paper presents two options of the parallel algorithm for finding the shortest covering of a large Boolean matrix, where the decomposition of the initial matrix into matrices of smaller sizes is based on the partitioning of rows. The parallel algorithm COVMB contains sequential algorithms for partitioning of initial m × n Boolean matrix on submatrices, building special matrices, summering of the shortest coverings of special Boolean matrices with smaller sizes as well as the sequential algorithm SECNOP for finding the shortest coverings of smaller Boolean matrices.