Geodesic
Packing of (0, 1)-matrices
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 519-535

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ita:2006037
Classification : 68Q17, 68Q25
Keywords: NP-hardness, $(0,1)$-matrix 
@article{ITA_2006__40_4_519_0,
     author = {Vialette, St\'ephane},
     title = {Packing of (0, 1)-matrices},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {519--535},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {4},
     year = {2006},
     doi = {10.1051/ita:2006037},
     mrnumber = {2277046},
     zbl = {1110.68049},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2006037/}
}
TY  - JOUR
AU  - Vialette, Stéphane
TI  - Packing of (0, 1)-matrices
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 519
EP  - 535
VL  - 40
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2006037/
DO  - 10.1051/ita:2006037
LA  - en
ID  - ITA_2006__40_4_519_0
ER  - 
%0 Journal Article
%A Vialette, Stéphane
%T Packing of (0, 1)-matrices
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 519-535
%V 40
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2006037/
%R 10.1051/ita:2006037
%G en
%F ITA_2006__40_4_519_0
Vialette, Stéphane. Packing of (0, 1)-matrices. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 519-535. doi: 10.1051/ita:2006037

Cité par Sources :