Finding All-One Hyper-Submatrix of an Incidence Matrix
| Autor: | Yongxin Zhu, Mengjun Li, Bin Liu, Weiwei Shi, Chang Wang, Yishu Mao |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Degree matrix Computer science 020209 energy MathematicsofComputing_NUMERICALANALYSIS Block matrix Graph theory Incidence matrix 02 engineering and technology Graph Combinatorics Matrix (mathematics) Distance matrix Cuthill–McKee algorithm Matrix of ones 0202 electrical engineering electronic engineering information engineering Bipartite graph Algorithm design Adjacency matrix Laplacian matrix Time complexity |
| Zdroj: | HPCC/SmartCity/DSS |
| DOI: | 10.1109/hpcc-smartcity-dss.2016.0149 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|