skip to main content

Outerplanar obstructions for matroid pathwidth

Koutsonas, Athanassios ; Thilikos, Dimitrios M. ; Yamazaki, Koichi

Discrete Mathematics, Feb 6, 2014, Vol.315-316, p.95(7) [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    Outerplanar obstructions for matroid pathwidth
  • Autor: Koutsonas, Athanassios ; Thilikos, Dimitrios M. ; Yamazaki, Koichi
  • Assuntos: Algorithms
  • É parte de: Discrete Mathematics, Feb 6, 2014, Vol.315-316, p.95(7)
  • Descrição: To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.disc.2013.10.007 Byline: Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki 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. Article History: Received 25 February 2012; Revised 25 July 2013; Accepted 9 October 2013
  • Idioma: English

Buscando em bases de dados remotas. Favor aguardar.