Partition of a Binary Matrix into ( ) Exclusive Row and Column Submatrices Is Difficult

Peiqiang Liu, Daming Zhu, Jinjie Xiao, Qingsong Xie and Yanyan Mao

Mathematical Problems in Engineering, 2014, vol. 2014, 1-13

Abstract:

A biclustering problem consists of objects and an attribute vector for each object. Biclustering aims at finding a bicluster—a subset of objects that exhibit similar behavior across a subset of attributes, or vice versa. Biclustering in matrices with binary entries (“0†/“1†) can be simplified into the problem of finding submatrices with entries of “1.†In this paper, we consider a variant of the biclustering problem: the -submatrix partition of binary matrices problem. The input of the problem contains an matrix with entries (“0†/“1†) and a constant positive integer . The -submatrix partition of binary matrices problem is to find exactly submatrices with entries of “1†such that these submatrices are pairwise row and column exclusive and each row (column) in the matrix occurs in exactly one of the submatrices. We discuss the complexity of the -submatrix partition of binary matrices problem and show that the problem is NP-hard for any by reduction from a biclustering problem in bipartite graphs.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2014/934630.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2014/934630.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:934630

DOI: 10.1155/2014/934630

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().