Theoretical Computer Science Asked by gsv on November 26, 2021
Suppose A and B are initial Boolean matrices. Let C = A*B. Suppose one can perform the sequence of the next operations: "set A[i,j] = 1", "set B[i,j] = 1". The result of each operation is a set of updated cells (not just affected, it is important that value is changed from 0 to 1) in matrix C. Is there any research on this problem? Can we do the update (theoretically) faster than in a naive way? For example, are there estimations on possible speedup by a logarithmic factor? The problem looks slightly similar to incremental transitive closure or dynamic matrix inverse, but quite specific.
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP