Permuting Matrices to Avoid Forbidden Submatrices
Permuting Matrices to Avoid Forbidden Submatrices
复制标题
排列矩阵以避免禁止子矩阵
DOI：
10.1016/0166-218x(94)00054-h
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
G. Woeginger
中科院分区：
文献类型：
--
作者：
Bettina Klinz;Rüdiger Rudolf;G. Woeginger
本文对一类自然的组合问题给出了一个框架，并指出这类问题包括许多重要的特殊情况。一个矩阵M被称为避开一组矩阵，如果M不包含任何元素。“作为（有序）子矩阵。F or.~本文讨论了矩阵的行和列是否可以置换的问题，使得所得矩阵M避免了矩阵中的所有矩阵。我们调查了几个已知的和新的结果，这个问题的算法的复杂性，主要是处理（0，l）-矩阵。除此之外，我们将证明这个问题对于许多集合是多项式时间可解的。“包含一个单一的，小矩阵，我们将展示一些例子集~其中的问题是NP完全的。
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. F or.~ a fixed set of matrices, we consider the pmbiem of deciding whether the rows and columns of a matrix can he 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, l)-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.