Name
Abstract | ||
|---|---|---|
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 HyperSubmatrix 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 algorithm we proposed is much better than Apriori algorithm, and a little worse than optimized PrefixSpan algorithm. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/HPCC-SmartCity-DSS.2016.105 | PROCEEDINGS OF 2016 IEEE 18TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING AND COMMUNICATIONS; IEEE 14TH INTERNATIONAL CONFERENCE ON SMART CITY; IEEE 2ND INTERNATIONAL CONFERENCE ON DATA SCIENCE AND SYSTEMS (HPCC/SMARTCITY/DSS) |
Field | DocType | Citations |
Adjacency matrix,Laplacian matrix,Combinatorics,Mathematical optimization,Computer science,Matrix of ones,Distance matrix,Degree matrix,Cuthill–McKee algorithm,Block matrix,Incidence matrix,Distributed computing | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bin Liu | 1 | 77 | 6.09 |
| Yongxin Zhu | 2 | 466 | 58.07 |
| chang wang | 3 | 33 | 12.55 |
| Mengjun Li | 4 | 0 | 0.34 |
| WeiWei Shi | 5 | 51 | 12.26 |
| Yishu Mao | 6 | 6 | 3.28 |