Finite integer index of pathwidth and treewidth

DOI10.1007/978-3-319-13524-3_22MaRDI QIDQ2946024zbMATH OpenOpenAlexFDO

Authors Jakub Gajarský, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Fernando Sánchez Villaamil, Somnath Sikdar, Peter Rossmanith

Publication date 15 September 2015

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-13524-3_22

Mathematics Subject Classification ID

Distance in graphs (05C12) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Kernel bounds for structural parameterizations of pathwidth
• Kernelization using structural parameters on sparse graph classes
• A quartic kernel for pathwidth-one vertex deletion
• scientific article; zbMATH DE number 176762
• Fixed-parameter tractability of treewidth and pathwidth

Cites work

• (Meta) Kernelization
• An algebraic theory of graph reduction
• Bidimensionality and kernels
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Graph theory
• Kernelization using structural parameters on sparse graph classes
• Reduction algorithms for graphs of small treewidth
• Sparsity. Graphs, structures, and algorithms
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

This page was built for publication: Finite integer index of pathwidth and treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946024)