Document
Services
-
Same authors
-
Related articles
- Recommend this article
- Download citation
- Alert me if this article is cited
- Alert me if this article is corrected
BibSonomy
CiteUlike
Connotea
Del.icio.us
Digg
Facebook
|
||||||||||||||||||
Theoret. Informatics Appl. 40, 519-535 (2006)
DOI: 10.1051/ita:2006037
Packing of (0, 1)-matrices
Stéphane VialetteLaboratoire de Recherche en Informatique (LRI), UMR 8623, Bât. 490, Université Paris-Sud, 91405 Orsay Cedex, France; Stephane.vialette@lri.fr
(Received June, 2002. Accepted June, 2004. Published online 8 November 2006.)
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.
Mathematics Subject Classification. 68Q17, 68Q25.
Key words: NP-hardness -- (0,1)-matrix.
© EDP Sciences 2006
| What is OpenURL? |
The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
- If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
- You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
- You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.