Reordering 2-d Binary Matrices Without Permutation Generation
Fatimah Binta Abdullahi · 2019
Matrix reordering is the arrangement of rows and columns in a given matrix to achieve a representation of the data. This paper presents heuristic methods for reordering rows and columns of 2-dimensional matrices. First, we show that our adopted heuristics can reorder 2-D matrices efficiently without considering permutation generation, an NP complete problem. Second, we evaluate the approach by comparing three heuristic methods to matrix reordering problem: a two-dimensional sort (2-D Sort), barycentre (BC) algorithm and the proposed 2-Dimensional Banding algorithm (2-D Banding). We conduct evaluation using randomly generated datasets and UCI datasets. This paper evaluates the heuristic methods using Average Distance (AD); the distance of nonzero entries from the leading diagonal and the computation time. The results presented shows that the proposed 2-D banding algorithm produced a minimized AD than the 2-D Sort and BC.