Permuting matrices to avoid forbidden submatrices

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

Research output: Contribution to journalArticleAcademicpeer-review

23 Citations (Scopus)

Abstract

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
Volume60
Issue number1-3
DOIs
Publication statusPublished - 1995

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

Cite this