0
$\begingroup$

In the following 0/1 matrix I'm trying to identify every largest submatrices formed by 1's as shown in the picture. Submatrices can have just one row only if they have more than 3 columns. Submatrices can have just one column only if they have more than 3 rows. Submatrices should have less than maxcol columns and maxrow rows and more than mincol and minrow. In the picture mincol=minrow=2. maxrow=maxcolumn=6. I've been searching for this problem, looks like an already studied problem but couldn't find it elsewhere.

enter image description here

$\endgroup$
  • $\begingroup$ This might be a programming question and not strictly a math question. (Are you trying to write a program to do that..? In what language?) You might want to try stackoverflow $\endgroup$ – TastySpaceApple Apr 6 '14 at 21:03
1
$\begingroup$

See https://stackoverflow.com/questions/14829451/how-can-i-find-all-contiguous-submatrices/14829533#14829533 . This gives an $O(n^2)$ preprocessing time step where you first compute the number of ones in the submatrix with corners $(0,0)$ and $(a,b)$ for all $a,b$. (If you do this by going through one column at a time you can do it in $O(n^2)$ time). Then for an arbitrary submatrix you can compute the number of ones in the submatrix in constant time using the preprocessing information (see the link). So you can just search over all submatrices that fit your constraints, and if you find a submatrix of all ones then you can use its size as a bound so you can skip smaller submatrices when you continue the search. (assuming that you only want submatrices of ones that have the maximum possible number of cells)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.