Matroid Pathwidth and Code Trellis Complexity
Matroid Pathwidth and Code Trellis Complexity
复制标题
拟阵路径宽度和代码网格复杂度
DOI：
10.1137/070691152
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
N. Kashyap
中科院分区：
文献类型：
--
作者：
N. Kashyap
我们将矩阵路径宽度的概念与线性代码的最小网格状态复杂度（我们称之为网格宽度）和图的路径宽度联系起来。通过简化计算图的路径宽度问题，我们证明了确定可表示矩阵的路径宽度问题是np困难的。因此，计算线性代码的网格宽度的问题也是np困难的。对于有限域$\F$，我们也考虑了$\F$的路径宽度不超过$w$的可表示矩阵类，以及相应的$\F$上的栅格宽度不超过$w$的线性码族。这些很容易被看作是小闭合。由于这些拟阵（和码）的分支宽度不超过$w$，因此Geelen和Whittle的结果表明，这些拟阵（和相应的码）具有有限多个排除子阵的特征。我们给出了$w=1$的排除子式的完整列表，并给出了$w=2$的部分列表。
We relate the notion of matroid pathwidth to the minimum trellis state-complexity (which we term trellis-width) of a linear code and to the pathwidth of a graph. By reducing from the problem of computing the pathwidth of a graph, we show that the problem of determining the pathwidth of a representable matroid is NP-hard. Consequently, the problem of computing the trellis-width of a linear code is also NP-hard. For a finite field $\F$, we also consider the class of $\F$-representable matroids of pathwidth at most $w$, and correspondingly, the family of linear codes over $\F$ with trellis-width at most $w$. These are easily seen to be minor-closed. Since these matroids (and codes) have branchwidth at most $w$, a result of Geelen and Whittle shows that such matroids (and the corresponding codes) are characterized by finitely many excluded minors. We provide the complete list of excluded minors for $w=1$ and give a partial list for $w=2$.