Zero-One Matrices Analysis of Algorithms and Problem Complexity Data Structures Models of Computation
Issue Date:
2007
Publisher:
Institute of Information Theories and Applications FOI ITHEA
Abstract:
In this paper we present algorithms which work on pairs of 0,1- matrices which multiply again a matrix
of zero and one entries. When applied over a pair, the algorithms change the number of non-zero entries present
in the matrices, meanwhile their product remains unchanged. We establish the conditions under which the
number of 1s decreases. We recursively define as well pairs of matrices which product is a specific matrix and
such that by applying on them these algorithms, we minimize the total number of non-zero entries present in both
matrices. These matrices may be interpreted as solutions for a well known information retrieval problem, and in
this case the number of 1 entries represent the complexity of the retrieve and information update operations.
