The MATRIX PACKING DOWN problem asks to find a row permutation of a given -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 -matrices or to -matrices with at most two ’s per column. Also, as intermediate results, we introduce several new simple graph layout problems which are proved to be NP-complete.
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita:2006037/
[1] Perfect graphs, in Studies in graph theory, edited by D.R. Fulkerson. Washington D.C., Math. Assoc. Amer. (1975) 1-22. | Zbl
,[2] Graph Classes: A Survey, SIAM, Philadelphia, SIAM Monogr. Discrete Math. Appl. (1999). | MR | Zbl
, and ,[3] Combinatorial Matrix Theory. Cambridge University Press, New York (1991). | MR | Zbl
and ,[4] On the complexity and approximation of syntenic distance. Discrete Appl. Math. 88 (1998) 59-82. | Zbl
, , , and ,[5] Approximating layout problems on random geometric graphs. J. Algorithms 39 (2001) 78-116. | Zbl
, , and ,[6] A survey on graph layout problems. ACM Comput. Surveys 34 (2002) 313-356.
, and ,[7] Graph theory. Number 173 in Graduate texts in Mathematics. Springer-Verlag, second edition (2000). | MR | Zbl
,[8] NP-completeness of several arrangement problems. Technical Report TR-43, Dept. of Computer Science, Haifa (1975).
and ,[9] Computers and Intractability: a guide to the theory of NP-completeness. W.H. Freeman, San Franciso (1979). | MR | Zbl
and ,[10] Some simplified NP-complete graph problems. Theor. Comput. Sci. 1 (1976) 237-267. | Zbl
, and ,[11] The intersection graphs of subtrees are exactly the chordal graphs. J. Combin. Theory Ser. B 16 (1974) 47-56. | Zbl
,[12] Some NP-complete problems on graphs, in Proc. of the 11th Conference on Information Sciences and Systems, John Hopkins University, Baltimore (1977) 91-95.
,[13] Four strikes against physical mapping of dna. J. Comput. Biology 2 (1995) 139-152.
, , and ,[14] Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). | MR | Zbl
,[15] Minimizing the profile of a symmetric matrix. SIAM J. Scientific Comput. 23 (2002) 1799-1816. | Zbl
,[16] Split graphs. Congr. Numer. 19 (1997) 311-315. | Zbl
and ,[17] Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math. 36 (1992) 153-168. | Zbl
and ,[18] On sparse matrix reordering for parallel factorization, in International Conference on Supercomputing (1994) 431-438.
, and ,[19] Topics in intersection graph theory. SIAM Monogr. Discrete Math. Appl. (1999). | MR | Zbl
and ,[20] The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebraic Discrete Methods 7 (1986) 505-512. | Zbl
,[21] Min Cut is NP-complete for edge weighted trees. Theor. Comput. Sci. 58 (1988) 209-229. | Zbl
and ,[22] The NP-completness of the bandwidth minimization problem. Computing 16 (1976) 263-270. | Zbl
,[23] A minimum linear arrangement algorithm for undirected trees. SIAM J. Comput. 30 (1979) 1173-1789. | Zbl
,[24] On crossing numbers, and some unsolved problems, in Combinatorics, Geometry and Probability: A Tribute to Paul Erdös, edited by B. Bollobás and A. Thomason, Cambridge University Press (1997) 557-562. | Zbl
,Cité par Sources :