Treewidth and pathwidth parameterized by the vertex cover number
From MaRDI portal
Publication:344839
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
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
