On the lossy kernelization for connected treedepth deletion set

DOI10.1007/978-3-031-15914-5_15OpenAlexW4312290949MaRDI QIDQ6043184

Diptapriyo Majumdar, Eduard Eiben, 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

kernelizationtreedepthlossy kernelizationconnected treedepth deletion set

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kernelization using structural parameters on sparse graph classes
• Forbidden graphs for tree-depth
• The kernelization complexity of connected domination in graphs with (no) small cycles
• Polynomial kernels for hitting forbidden minors under structural parameterizations
• On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
• A completeness theory for polynomial (Turing) kernelization
• Tree-depth, subgraph coloring and homomorphism bounds
• Deterministic Parameterized Connected Vertex Cover
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Uniform Kernelization Complexity of Hitting Forbidden Minors
• Thek-Steiner Ratio in Graphs
• Kernelization Lower Bounds Through Colors and IDs
• Lossy kernelization
• Kernelization Lower Bounds by Cross-Composition
• A Faster Parameterized Algorithm for Treedepth
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• Steiner Tree Approximation via Iterative Randomized Rounding
• Parameterized Algorithms
• The steiner problem in graphs
• On Approximate Compressions for Connected Minor-Hitting Sets.

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