Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/698

 Title: Algorithmic Minimization of Non-zero Entries in 0,1-Matrices Authors: Toni, AdrianaCastellanos, JuanErviti, Jose Keywords: Zero-One MatricesAnalysis of Algorithms and Problem ComplexityData StructuresModels 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. URI: http://hdl.handle.net/10525/698 ISSN: 1313-0463 Appears in Collections: Volume 14 Number 4

Files in This Item:

File Description SizeFormat