Packing of (0, 1)-matrices

Stéphane Vialette

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 4, page 519-535
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Vialette, Stéphane. "Packing of (0, 1)-matrices." RAIRO - Theoretical Informatics and Applications 40.4 (2006): 519-535. <http://eudml.org/doc/249712>.

@article{Vialette2006,
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. },
author = {Vialette, Stéphane},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {NP-hardness; (0,1)-matrix.},
language = {eng},
month = {11},
number = {4},
pages = {519-535},
publisher = {EDP Sciences},
title = {Packing of (0, 1)-matrices},
url = {http://eudml.org/doc/249712},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Vialette, Stéphane
TI - Packing of (0, 1)-matrices
JO - RAIRO - Theoretical Informatics and Applications
DA - 2006/11//
PB - EDP Sciences
VL - 40
IS - 4
SP - 519
EP - 535
AB - 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.
LA - eng
KW - NP-hardness; (0,1)-matrix.
UR - http://eudml.org/doc/249712
ER -

References

top
  1. C. Berge, Perfect graphs, in Studies in graph theory, edited by D.R. Fulkerson. Washington D.C., Math. Assoc. Amer. (1975) 1–22.  Zbl0329.05118
  2. A. Brandstädt, V. Bang Le and J.P. Spinrad, Graph Classes: A Survey, SIAM, Philadelphia, SIAM Monogr. Discrete Math. Appl. (1999).  
  3. R.A. Brualdi and H.J. Ryser, Combinatorial Matrix Theory. Cambridge University Press, New York (1991).  
  4. B. DasGupta, T. Jiang, S. Kannan, M. Li and E. Sweedyk, On the complexity and approximation of syntenic distance. Discrete Appl. Math.88 (1998) 59–82.  Zbl0928.68057
  5. J. Dìaz, M.D. Penrose, J. Petit and M. Serna, Approximating layout problems on random geometric graphs. J. Algorithms39 (2001) 78–116.  Zbl0974.68148
  6. J. Dìaz, J. Petit and M. Serna, A survey on graph layout problems. ACM Comput. Surveys34 (2002) 313–356.  
  7. R. Diestel, Graph theory. Number 173 in Graduate texts in Mathematics. Springer-Verlag, second edition (2000).  
  8. S. Even and Y. Shiloach, NP-completeness of several arrangement problems. Technical Report TR-43, Dept. of Computer Science, Haifa (1975).  
  9. M.R. Garey and D.S. Johnson, Computers and Intractability: a guide to the theory of NP-completeness. W.H. Freeman, San Franciso (1979).  Zbl0411.68039
  10. M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems. Theor. Comput. Sci.1 (1976) 237–267.  Zbl0338.05120
  11. F. Gavril, The intersection graphs of subtrees are exactly the chordal graphs. J. Combin. Theory Ser. B16 (1974) 47–56.  Zbl0266.05101
  12. 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.  
  13. P.W. Goldberg, M.C. Golumbic, H. Kaplan and R. Shamir, Four strikes against physical mapping of dna. J. Comput. Biology2 (1995) 139–152.  
  14. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980).  Zbl0541.05054
  15. W.W. Hager, Minimizing the profile of a symmetric matrix. SIAM J. Scientific Comput.23 (2002) 1799–1816.  Zbl1014.65020
  16. P.L. Hammer and S. Foldes, Split graphs. Congr. Numer.19 (1997) 311–315.  
  17. M. Juvan and B. Mohar, Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math.36 (1992) 153–168.  Zbl0759.05087
  18. B. Kumar, P. Sadayappan and C.-H. Huang, On sparse matrix reordering for parallel factorization, in International Conference on Supercomputing (1994) 431–438.  
  19. T.A. McKee and F.R. McMorris, Topics in intersection graph theory. SIAM Monogr. Discrete Math. Appl. (1999).  Zbl0945.05003
  20. B. Monien, The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebraic Discrete Methods7 (1986) 505–512.  Zbl0624.68059
  21. B. Monien and I.H. Sudborough, Min Cut is NP-complete for edge weighted trees. Theor. Comput. Sci.58 (1988) 209–229.  Zbl0657.68034
  22. C.H. Papadimitriou, The NP-completness of the bandwidth minimization problem. Computing16 (1976) 263–270.  Zbl0321.65019
  23. Y. Shiloach, A minimum linear arrangement algorithm for undirected trees. SIAM J. Comput.30 (1979) 1173–1789.  Zbl0399.05021
  24. 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.  Zbl0879.05022

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.