skip to main content

Sair
Identificação

Idioma:

Outerplanar obstructions for matroid pathwidth

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

Discrete mathematics, 2014-02, Vol.315-316, p.95-101 [Periódico revisado por pares]

Elsevier B.V

Texto completo disponível

Citações Citado por

Enviar para

Título:
Outerplanar obstructions for matroid pathwidth
Autor: Koutsonas, Athanassios ; Thilikos, Dimitrios M. ; Yamazaki, Koichi
Assuntos: Algorithms ; Computational Complexity ; Computer Science ; Decomposition ; Discrete Mathematics ; Graphs ; Integers ; Lower bounds ; Mathematical analysis ; Matroids ; Obstructions ; Outerplanar graphs ; Pathwidth ; Proving
É parte de: Discrete mathematics, 2014-02, Vol.315-316, p.95-101
Notas: ObjectType-Article-1
SourceType-Scholarly Journals-1
ObjectType-Feature-2
Descrição: 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.
Editor: Elsevier B.V
Idioma: Inglês

Links

View record in HAL

Voltar para lista de resultados

Realização: Logos de Redes Sociais:

Buscando em bases de dados remotas. Favor aguardar.

Buscando por
emscope:(USP_VIDEOS),scope:("PRIMO"),scope:(USP_FISICO),scope:(USP_EREVISTAS),scope:(USP),scope:(USP_EBOOKS),scope:(USP_PRODUCAO),primo_central_multiple_fe
Mostrar o que foi encontrado até o momento