Matroid Pathwidth and Code Trellis Complexity
| dc.creator | Kashyap, Navin | |
| dc.date | 2007-05-10 | |
| dc.date.accessioned | 2026-07-07T08:16:04Z | |
| dc.date.available | 2026-07-07T08:16:04Z | |
| dc.description | 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$. | |
| dc.description | Submitted to SIAM Journal on Discrete Mathematics; 18 pages, 6 figures | |
| dc.identifier | https://arxiv.org/abs/0705.1384 | |
| dc.identifier | http://arxiv.org/abs/0705.1384 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/133656 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Information Theory | |
| dc.title | Matroid Pathwidth and Code Trellis Complexity | |
| dc.type | text |