Outerplanar Obstructions for Matroid Pathwidth

Athanassios Koutsonas; Dimitrios M. Thilikos; Koichi Yamazaki

doi:10.1016/j.endm.2011.09.088

Outerplanar Obstructions for Matroid Pathwidth

Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

For each 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.

Original language	English (US)
Pages (from-to)	541-546
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	38
DOIs	https://doi.org/10.1016/j.endm.2011.09.088
State	Published - Dec 1 2011

Keywords

Linear-width
Matroid Pathwidth
Outerplanar Graphs
Pathwidth

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2011.09.088

Cite this

@article{808911dca496431d9eaa663730affa22,

title = "Outerplanar Obstructions for Matroid Pathwidth",

abstract = "For each 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.",

keywords = "Linear-width, Matroid Pathwidth, Outerplanar Graphs, Pathwidth",

author = "Athanassios Koutsonas and Thilikos, {Dimitrios M.} and Koichi Yamazaki",

year = "2011",

month = dec,

day = "1",

doi = "10.1016/j.endm.2011.09.088",

language = "English (US)",

volume = "38",

pages = "541--546",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Outerplanar Obstructions for Matroid Pathwidth

AU - Koutsonas, Athanassios

AU - Thilikos, Dimitrios M.

AU - Yamazaki, Koichi

PY - 2011/12/1

Y1 - 2011/12/1

N2 - For each 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.

AB - For each 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.

KW - Linear-width

KW - Matroid Pathwidth

KW - Outerplanar Graphs

KW - Pathwidth

UR - http://www.scopus.com/inward/record.url?scp=82955245391&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=82955245391&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2011.09.088

DO - 10.1016/j.endm.2011.09.088

M3 - Article

AN - SCOPUS:82955245391

SN - 1571-0653

VL - 38

SP - 541

EP - 546

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Outerplanar Obstructions for Matroid Pathwidth

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this