The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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...
Bref survol du théorème de non-plongement de J. Cheeger et B. Kleiner pour le groupe d’Heisenberg dans .
We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class of all -padded sets, if it is a subset of ). This is a continuation of the research of reducibilities to sparse and tally sets that were studied in many previous papers (for a good survey see [HOW1]). We show necessary and sufficient conditions to collapse and separate classes of bounded truth-table reducibilities to padded sets. We prove that depending on two properties of a...
Currently displaying 1 –
3 of
3