Permuting matrices to avoid forbidden submatrices

B. Klinz, R. Rudolf, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    21 Citations (Scopus)


    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.
    Original languageEnglish
    Pages (from-to)223-248
    JournalDiscrete Applied Mathematics
    Issue number1-3
    Publication statusPublished - 1995


    Dive into the research topics of 'Permuting matrices to avoid forbidden submatrices'. Together they form a unique fingerprint.

    Cite this