TY - JOUR

T1 - Permuting matrices to avoid forbidden submatrices

AU - Klinz, B.

AU - Rudolf, R.

AU - Woeginger, G.J.

PY - 1995

Y1 - 1995

N2 - This paper attaches a frame to a natural class of combinatorial problems and points out that this class includes many important special cases.
A matrix M is said to avoid a set of matrices if M does not contain any element of as (ordered) submatrix. For a fixed set of matrices, we consider the problem of deciding whether the rows and columns of a matrix can be permuted in such a way that the resulting matrix M avoids all matrices in .
We survey several known and new results on the algorithmic complexity of this problem, mostly dealing with (0,1)-matrices. Among others, we will prove that the problem is polynomial time solvable for many sets containing a single, small matrix and we will exhibit some example sets for which the problem is NP-complete.

AB - This paper attaches a frame to a natural class of combinatorial problems and points out that this class includes many important special cases.
A matrix M is said to avoid a set of matrices if M does not contain any element of as (ordered) submatrix. For a fixed set of matrices, we consider the problem of deciding whether the rows and columns of a matrix can be permuted in such a way that the resulting matrix M avoids all matrices in .
We survey several known and new results on the algorithmic complexity of this problem, mostly dealing with (0,1)-matrices. Among others, we will prove that the problem is polynomial time solvable for many sets containing a single, small matrix and we will exhibit some example sets for which the problem is NP-complete.

U2 - 10.1016/0166-218X(94)00054-H

DO - 10.1016/0166-218X(94)00054-H

M3 - Article

SN - 0166-218X

VL - 60

SP - 223

EP - 248

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -