Affiliations: [a] Department of Algorithms And Their Applications, Faculty of Informatics, Eötvös Loránd University, Pázmány Péter sétány 1/C, H-1117, Budapest, Hungary. [email protected] | [b] Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2. H-6720, Szeged, Hungary. [email protected]
Note: [*] Address for correspondence: Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2. H-6720, Szeged, Hungary
Abstract: Analysis of patterns in binary matrices plays a vital role in numerous applications of computer science. One of the most essential patterns of such matrices are the so called switching components, where the number and location of the components gives valuable information about the binary matrix. One way to measure the effect of switching components in a binary matrix is counting the number of 0-s which have to be replaced with 1-s in order to eliminate the switching components. However, finding the minimal number of 0-1 flips is generally an NP-complete problem. We present two novel-type heuristics for the above problem and show via experiments that they outperform the formerly proposed ones, both in optimality and in running time. We also show how to use those heuristics for determining the so-called nestedness level of a matrix, and how to use the flips for binary image compression.
