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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2013, 315-316, pp.95-101. 〈10.1016/j.disc.2013.10.007〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083516
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 17 novembre 2014 - 13:52:13
Dernière modification le : samedi 25 novembre 2017 - 01:08:18
Document(s) archivé(s) le : vendredi 14 avril 2017 - 13:44:39

Fichier

mpath.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

49

Téléchargements de fichiers

170