Nonredundant 1's in Gamma-Free Matrices
Nonredundant 1's in Gamma-Free Matrices
复制标题
无伽玛矩阵中的非冗余 1
DOI：
--
复制
发表时间：
1995
影响因子：
0.8
通讯作者：
J. Spinrad
中科院分区：
文献类型：
--
作者：
J. Spinrad
本文研究了一种代表$ \ gamma $的新方法，该矩阵发生在弦弦两分和强烈的和弦图的特征中。我们表明，具有$ n $行和列的$ \ gamma $ - free矩阵的数量（因此，带有$ n $ vertices的弦弦两部分的数量和强烈的和弦图与$ 2^\ theta（n \ log^ {2} n）$，并给出一个渐近空间的最佳方法来存储这些矩阵。
This paper studies a new method for representing $\Gamma$-free matrices, which occur in characterizations of chordal bipartite and strongly chordal graphs. We show that the number of $\Gamma$-free matrices with $n$ rows and columns (and thus the number of chordal bipartite and strongly chordal graphs with $n$ vertices) is proportional to $2^\Theta(n \log^{2} n)$, and give an asymptotically space optimal method for storing these matrices.