Packing of (0, 1)-matrices
Laboratoire de Recherche en Informatique (LRI),
UMR 8623, Bât. 490, Université Paris-Sud,
91405 Orsay Cedex, France;
Accepted: June 2004
The MATRIX PACKING DOWN problem asks to find a row permutation of a given (0,1)-matrix in such a way that the total sum of the first non-zero column indexes is maximized. We study the computational complexity of this problem. We prove that the MATRIX PACKING DOWN problem is NP-complete even when restricted to zero trace symmetric (0,1)-matrices or to (0,1)-matrices with at most two 1's per column. Also, as intermediate results, we introduce several new simple graph layout problems which are proved to be NP-complete.
Mathematics Subject Classification: 68Q17 / 68Q25
Key words: NP-hardness / (0,1)-matrix.
© EDP Sciences, 2006