Packing of (0, 1)-matrices
RAIRO - Theoretical Informatics and Applications (2006)
- Volume: 40, Issue: 4, page 519-535
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topVialette, 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- 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).
- 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.
- J. Dìaz, M.D. Penrose, J. Petit and M. Serna, Approximating layout problems on random geometric graphs. J. Algorithms39 (2001) 78–116.
- J. Dìaz, J. Petit and M. Serna, A survey on graph layout problems. ACM Comput. Surveys34 (2002) 313–356.
- 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).
- M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems. Theor. Comput. Sci.1 (1976) 237–267.
- F. Gavril, The intersection graphs of subtrees are exactly the chordal graphs. J. Combin. Theory Ser. B16 (1974) 47–56.
- 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.
- P.W. Goldberg, M.C. Golumbic, H. Kaplan and R. Shamir, Four strikes against physical mapping of dna. J. Comput. Biology2 (1995) 139–152.
- M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980).
- W.W. Hager, Minimizing the profile of a symmetric matrix. SIAM J. Scientific Comput.23 (2002) 1799–1816.
- P.L. Hammer and S. Foldes, Split graphs. Congr. Numer.19 (1997) 311–315.
- M. Juvan and B. Mohar, Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math.36 (1992) 153–168.
- 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).
- B. Monien, The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebraic Discrete Methods7 (1986) 505–512.
- B. Monien and I.H. Sudborough, Min Cut is NP-complete for edge weighted trees. Theor. Comput. Sci.58 (1988) 209–229.
- C.H. Papadimitriou, The NP-completness of the bandwidth minimization problem. Computing16 (1976) 263–270.
- Y. Shiloach, 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.
NotesEmbed ?
topYou 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.