Outerplanar obstructions for matroid pathwidth - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2013

Outerplanar obstructions for matroid pathwidth

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Licence

Paternité

Identifiants

Citer

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 Consultations
245 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More