Finding All-One Hyper-Submatrix of an Incidence Matrix
Bin Liu, Yongxin Zhu, Chang Wang, Mengjun Li, Weiwei Shi, Yishu Mao · 2016
Nowadays, graph theory and matrix theory are developing very rapidly. Solutions to mathematical matrix and graph problems can be applied to solve many realistic problems. Finding submatrix of a specific matrix that satisfies specific constrains is a common and hard problem. Finding all-one submatrix of incidence matrix is a meaningful problem. But for most researches, they focus on finding all-one submatrix that elements of which are adjacent ones. Problem for finding all-one submtrix composed of ones that across rows and columns are not well solved. In this paper, we tried to solve this problem. First, we defined conceptions of Hyper-Submatrix, Maximum Hyper-Submatrix and N order Hyper Submatrix of incidence matrix. Then we come up with two mathematical problems. Problem 1 is how to find Maximum Hyper-Submatrix of an incidence matrix. Problem 2 is how to find N order Hyper-Submatrix of an incidence matrix. For problem 1, we come up with method based on graph theory. An upper bound of size of all-one submatrix of the incidence matrix is obtained with the result of problem 1. For problem 2, we come up with Algorithm 2 to solve it. Time complexity and space complexity are analyzed. Optimized algorithm are proposed and time complexity is optimized to O(m[n(n+1)]/2). Comparison experiments illustrate performance of 2 algorithm we proposed is much better than Apriori algorithm, and a little worse than optimized PrefixSpan algorithm.