Treewidth and pathwidth parameterized by the vertex cover number

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

Mathieu Liedloff, Mathieu Chapelle, Yngve Villanger, 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

treewidthpathwidthvertex coverparameterized algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On cutwidth parameterized by vertex cover
• Exact exponential algorithms.
• A note on exact algorithms for vertex ordering problems on graphs
• Improved upper bounds for vertex cover
• The vertex separation number of a graph equals its path-width
• Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
• On sparsification for computing treewidth
• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• Kernel Bounds for Structural Parameterizations of Pathwidth
• On exact algorithms for treewidth
• Finding Induced Subgraphs via Minimal Triangulations
• A Dynamic Programming Approach to Sequencing Problems
• Fourier meets M\"{o}bius: fast subset convolution
• A Parameterized Algorithm for Chordal Sandwich
• Graph Layout Problems Parameterized by Vertex Cover
• Computing Directed Pathwidth in O(1.89 n ) Time
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth