Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T00:56:23.738Z Has data issue: false hasContentIssue false

Packing of (0, 1)-matrices

Published online by Cambridge University Press:  08 November 2006

Stéphane Vialette*
Affiliation:
Laboratoire de Recherche en Informatique (LRI), UMR 8623, Bât. 490, Université Paris-Sud, 91405 Orsay Cedex, France; Stephane.vialette@lri.fr
Get access

Abstract

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.

Information

Type
Research Article
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable