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

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

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More