| Автор | Vialette, Stéphane |
| Дата выпуска | 2006 |
| dc.description | 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. |
| Формат | application.pdf |
| Издатель | EDP Sciences |
| Копирайт | © EDP Sciences, 2006 |
| Тема | NP-hardness |
| Тема | (0,1)-matrix. |
| Название | Packing of (0, 1)-matrices |
| Тип | research-article |
| DOI | 10.1051/ita:2006037 |
| Electronic ISSN | 1290-385X |
| Print ISSN | 0988-3754 |
| Журнал | RAIRO - Theoretical Informatics and Applications |
| Том | 40 |
| Первая страница | 519 |
| Последняя страница | 535 |
| Аффилиация | Vialette Stéphane; Laboratoire de Recherche en Informatique (LRI), UMR 8623, Bât. 490, Université Paris-Sud, 91405 Orsay Cedex, France; Stephane.vialette@lri.fr |
| Выпуск | 4 |
