Outerplanar obstructions for matroid pathwidth - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Mathematics Year : 2013

Outerplanar obstructions for matroid pathwidth

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.
Fichier principal
Vignette du fichier
mpath.pdf (3.4 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01083516 , version 1 (17-11-2014)

Licence

Attribution

Identifiers

Cite

Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki. Outerplanar obstructions for matroid pathwidth. Discrete Mathematics, 2013, 315-316, pp.95-101. ⟨10.1016/j.disc.2013.10.007⟩. ⟨lirmm-01083516⟩

Collections

LIRMM TDS-MACS
60 View
242 Download

Altmetric

Share

Gmail Facebook X LinkedIn More