On the lossy kernelization for connected treedepth deletion set

DOI10.1007/978-3-031-15914-5_15MaRDI QIDQ6043184zbMATH OpenOpenAlexFDO

Authors Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan

Publication date 5 May 2023

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-15914-5_15

zbMATH Keywords

connected treedepth deletion setkernelizationlossy kernelizationtreedepth

Mathematics Subject Classification ID

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

Cites work

• A completeness theory for polynomial (Turing) kernelization
• A faster parameterized algorithm for treedepth
• An approximate kernel for connected feedback vertex set
• Deterministic parameterized connected vertex cover
• Forbidden graphs for tree-depth
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 7053262 (Why is no real title available?)
• scientific article; zbMATH DE number 7650914 (Why is no real title available?)
• Kernelization Lower Bounds by Cross-Composition
• Kernelization lower bounds through colors and IDs
• Kernelization using structural parameters on sparse graph classes
• Lossy kernelization
• Lossy kernels for connected dominating set on sparse graphs
• On Approximate Compressions for Connected Minor-Hitting Sets.
• On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
• Parameterized algorithms
• Polynomial kernels for hitting forbidden minors under structural parameterizations
• Steiner tree approximation via iterative randomized rounding
• The kernelization complexity of connected domination in graphs with (no) small cycles
• The steiner problem in graphs
• Thek-Steiner Ratio in Graphs
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(1)

• Approximate Turing kernelization for problems parameterized by treewidth

This page was built for publication: On the lossy kernelization for connected treedepth deletion set

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