Treedepth Parameterized by Vertex Cover Number.

DOI10.4230/LIPIcs.IPEC.2016.18zbMath1398.68247MaRDI QIDQ4634401

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 cover; polynomial kernelization; fixed-parameter algorithm; structural parameterization; treedepth

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

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

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Maximum Minimal Vertex Cover Parameterized by Vertex Cover, Unnamed Item