Treewidth and pathwidth parameterized by the vertex cover number

DOI10.1016/j.dam.2014.12.012zbMath1350.68136arXiv1305.0433MaRDI QIDQ344839

Yngve Villanger, Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca

Publication date: 24 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.0433

zbMATH Keywords

treewidth; pathwidth; vertex cover; parameterized algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)