Outerplanar obstructions for matroid pathwidth

Abstract : This article appeared in a journal published by Elsevier. The attached copy is furnished to the author for internal non-commercial research and education use, including for instruction at the authors institution and sharing with colleagues. Other uses, including reproduction and distribution, or selling or licensing copies, or posting to personal, institutional or third party websites are prohibited. In most cases authors are permitted to post their version of the article (e.g. in Word or Tex form) to their personal website or institutional repository. Authors requiring further information regarding Elsevier's archiving and manuscript policies are encouraged to visit: http://www.elsevier.com/authorsrights a b s t r a c t 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, 2014, 315, pp.95-101. 〈10.1016/j.disc.2013.10.007〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01225581
Contributeur : Dimitrios M. Thilikos <>
Soumis le : vendredi 6 novembre 2015 - 12:36:04
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : lundi 8 février 2016 - 12:57:05

Fichier

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

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

35

Téléchargements de fichiers

74