Back to Search
Start Over
Outerplanar Obstructions for Matroid Pathwidth.
- Source :
- Electronic Notes in Discrete Mathematics; Dec2011, Vol. 38, p541-546, 6p
- Publication Year :
- 2011
-
Abstract
- Abstract: For each k, we provide all outerplanar obstructions for the class of graphs whose cycle matroid has pathwidth at most k. Our proof combines a decomposition lemma for proving lower bounds on matroid pathwidth and a relation between matroid pathwidth and linear-width. Our results imply the existence of a linear algorithm that, given an outerplanar graph, outputs its matroid pathwidth. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 15710653
- Volume :
- 38
- Database :
- Supplemental Index
- Journal :
- Electronic Notes in Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 69630528
- Full Text :
- https://doi.org/10.1016/j.endm.2011.09.088