Name
Abstract | ||
|---|---|---|
For each non-negative integer 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.disc.2013.10.007 | Discrete Mathematics |
Keywords | DocType | Volume |
cycle matroid,outerplanar obstruction,outerplanar graph,non-negative integer k,decomposition lemma,lower bound,linear width,linear algorithm,matroid pathwidth,pathwidth | Journal | 315-316, |
ISSN | Citations | PageRank |
0012-365X | 3 | 0.39 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Athanassios Koutsonas | 1 | 10 | 1.51 |
| Dimitrios M. Thilikos | 2 | 1844 | 124.72 |
| Koichi Yamazaki | 3 | 222 | 21.85 |