Is there a polynomial time solution to sort an arbitrary binary square matrix in polynomial time by rows so that the diagonal contains a 1 if any row contains a 1 in that column?
For example given matrix:
0 1 1 1 0 r0
1 0 0 1 0 r1
1 1 1 0 1 r2
0 0 0 0 1 r3
0 0 0 1 1 r4
A solution would be:
1 0 0 1 0 r1
1 1 1 0 1 r2
0 1 1 1 0 r0
0 0 0 1 1 r4
0 0 0 0 1 r3
Given a matrix:
1 0 0 r0
0 0 1 r1
1 0 1 r2
There could be multiple solutions:
1 0 0 r0 1 0 1 r2
0 0 1 r1 1 0 0 r0
1 0 1 r2 0 0 1 r1
No comments:
Post a Comment