论文标题
矩阵的强可合作图和无斜线订购
Strong cocomparability graphs and Slash-free orderings of matrices
论文作者
论文摘要
我们介绍了一类强的可可比较图，因为可以通过同时行和列置换量将其邻接矩阵的反射图等级重新排列，以避免使用行01、10的子序列，我们称之为slash。 我们为班级提供了订购表征，禁止结构表征和多项式时间识别算法。这些结果完成了图片，除了斜线矩阵外，除了斜线矩阵外，还有伽马矩阵（该行11、10）。众所周知，在这两种情况下，一个人分别获得了间隔图和强烈的弦图等级。 通过互补，我们获得了一类强可比性图，它们的邻接矩阵可以通过同时行和列置换来重新排列，以避免二下的两个身份subpatrix。因此，我们的结果还为这类反射图提供了特征和算法。换句话说，我们的结果可以解释为解决以下问题：给定具有0-二维亚质的对称的0,1-matrix，是否可以同时置换行和列以避免两乘二的身份subsatrix？
We introduce the class of strong cocomparability graphs, as the class of reflexive graphs whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the submatrix with rows 01, 10, which we call Slash. We provide an ordering characterization, a forbidden structure characterization, and a polynomial-time recognition algorithm, for the class. These results complete the picture in which in addition to, or instead of, the Slash matrix one forbids the Gamma matrix (which has rows 11, 10). It is well known that in these two cases one obtains the class of interval graphs, and the class of strongly chordal graphs, respectively. By complementation, we obtain the class of strong comparability graphs, whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the two-by-two identity submatrix. Thus our results give characterizations and algorithms for this class of irreflexive graphs as well. In other words, our results may be interpreted as solving the following problem: given a symmetric 0,1-matrix with 0-diagonal, can the rows and columns of be simultaneously permuted to avoid the two-by-two identity submatrix?
