Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-24T02:23:58.360Z Has data issue: false hasContentIssue false
  • English
  • Français

Packing of (0, 1)-matrices

Published online by Cambridge University Press:  08 November 2006

Stéphane Vialette
Stéphane Vialette*
Affiliation:
Laboratoire de Recherche en Informatique (LRI), UMR 8623, Bât. 490, Université Paris-Sud, 91405 Orsay Cedex, France; [email protected]
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.

Keywords

NP-hardness(0,1)-matrix.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 4 , October 2006 , pp. 519 - 535
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.)

References

C. Berge, Perfect graphs, in Studies in graph theory, edited by D.R. Fulkerson. Washington D.C., Math. Assoc. Amer. (1975) 1–22.
A. Brandstädt, V. Bang Le and J.P. Spinrad, Graph Classes: A Survey, SIAM, Philadelphia, SIAM Monogr. Discrete Math. Appl. (1999).
R.A. Brualdi and H.J. Ryser, Combinatorial Matrix Theory. Cambridge University Press, New York (1991).
DasGupta, B., Jiang, T., Kannan, S., Li, M. and Sweedyk, E., On the complexity and approximation of syntenic distance. Discrete Appl. Math. 88 (1998) 59–82. CrossRef
Dìaz, J., Penrose, M.D., Petit, J. and Serna, M., Approximating layout problems on random geometric graphs. J. Algorithms 39 (2001) 78–116. CrossRef
Dìaz, J., Petit, J. and Serna, M., A survey on graph layout problems. ACM Comput. Surveys 34 (2002) 313–356. CrossRef
R. Diestel, Graph theory. Number 173 in Graduate texts in Mathematics. Springer-Verlag, second edition (2000).
S. Even and Y. Shiloach, NP-completeness of several arrangement problems. Technical Report TR-43, Dept. of Computer Science, Haifa (1975).
M.R. Garey and D.S. Johnson, Computers and Intractability: a guide to the theory of NP-completeness. W.H. Freeman, San Franciso (1979).
Garey, M.R., Johnson, D.S. and Stockmeyer, L., Some simplified NP-complete graph problems. Theor. Comput. Sci. 1 (1976) 237–267. CrossRef
Gavril, F., The intersection graphs of subtrees are exactly the chordal graphs. J. Combin. Theory Ser. B 16 (1974) 47–56. CrossRef
F. Gavril, Some NP-complete problems on graphs, in Proc. of the 11th Conference on Information Sciences and Systems, John Hopkins University, Baltimore (1977) 91–95.
Goldberg, P.W., Golumbic, M.C., Kaplan, H. and Shamir, R., Four strikes against physical mapping of dna. J. Comput. Biology 2 (1995) 139–152. CrossRef
M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980).
Hager, W.W., Minimizing the profile of a symmetric matrix. SIAM J. Scientific Comput. 23 (2002) 1799–1816. CrossRef
Hammer, P.L. and Foldes, S., Split graphs. Congr. Numer. 19 (1997) 311–315.
Juvan, M. and Mohar, B., Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math. 36 (1992) 153–168. CrossRef
B. Kumar, P. Sadayappan and C.-H. Huang, On sparse matrix reordering for parallel factorization, in International Conference on Supercomputing (1994) 431–438.
T.A. McKee and F.R. McMorris, Topics in intersection graph theory. SIAM Monogr. Discrete Math. Appl. (1999).
Monien, B., The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebraic Discrete Methods 7 (1986) 505–512. CrossRef
Monien, B. and Sudborough, I.H., Min Cut is NP-complete for edge weighted trees. Theor. Comput. Sci. 58 (1988) 209–229. CrossRef
Papadimitriou, C.H., The NP-completness of the bandwidth minimization problem. Computing 16 (1976) 263–270. CrossRef
Shiloach, Y., A minimum linear arrangement algorithm for undirected trees. SIAM J. Comput. 30 (1979) 1173–1789.
H.S. Wilf, 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.