Treedepth Parameterized by Vertex Cover Number.

DOI10.4230/LIPICS.IPEC.2016.18MaRDI QIDQ4634401zbMATH OpenOpenAlexFDO

Authors Yasuaki Kobayashi, Hisao Tamaki

Publication date 10 April 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.IPEC.2016.18

zbMATH Keywords

vertex coverfixed-parameter algorithmpolynomial kernelizationstructural parameterizationtreedepth

Mathematics Subject Classification ID

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

Recommendations

• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• Treewidth and pathwidth parameterized by the vertex cover number
• Tree-depth and vertex-minors
• On the tree cover number of a graph
• scientific article; zbMATH DE number 5775505
• A faster parameterized algorithm for treedepth
• Vertex cover and edge-vertex domination in trees
• Branch-depth: generalizing tree-depth of graphs
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Exploring the gap between treedepth and vertex cover through vertex integrity

Cited in

(10)

• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• A graph searching game for block treedepth and a cubic kernel by vertex cover
• A faster parameterized algorithm for treedepth
• scientific article; zbMATH DE number 7764119 (Why is no real title available?)
• scientific article; zbMATH DE number 7764121 (Why is no real title available?)
• Maximum minimal vertex cover parameterized by vertex cover
• Treewidth and pathwidth parameterized by the vertex cover number
• Computing kernels in parallel: lower and upper bounds
• The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.
• Exploring the gap between treedepth and vertex cover through vertex integrity

This page was built for publication: Treedepth Parameterized by Vertex Cover Number.

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