On approximate preprocessing for domination and hitting subgraphs with connected deletion sets

DOI10.1016/J.JCSS.2019.05.001MaRDI QIDQ2316936zbMATH OpenOpenAlexFDO

Authors Eduard Eiben, Danny Hermelin, M. S. Ramanujan

Publication date 7 August 2019

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2019.05.001

zbMATH Keywords

kernelizationparameterized complexityvertex deletion problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Lossy Kernels for Hitting Subgraphs
• Lossy kernelization
• Lossy kernels for connected dominating set on sparse graphs
• Lossy kernels for connected dominating set on sparse graphs
• On the approximate compressibility of connected vertex cover

Cites work

• (Meta) kernelization
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• scientific article; zbMATH DE number 1263241 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Intersection Theorems for Systems of Sets
• Kernelization -- preprocessing with a guarantee
• Kernelization and Sparseness: the case of Dominating Set
• Kernelization lower bounds through colors and IDs
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Lossy kernelization
• Lossy kernels for connected dominating set on sparse graphs
• Parameterized algorithms
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Polynomial-time data reduction for dominating set
• Recent developments in kernelization: a survey
• Steiner tree approximation via iterative randomized rounding
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• The steiner problem in graphs
• Tight approximation bounds for dominating set on graphs of bounded arboricity

Cited in

(6)

• \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
• Lossy kernels for connected dominating set on sparse graphs
• Lossy Kernels for Hitting Subgraphs
• Lossy kernels for connected dominating set on sparse graphs
• On the lossy kernelization for connected treedepth deletion set
• Approximate Turing kernelization for problems parameterized by treewidth

This page was built for publication: On approximate preprocessing for domination and hitting subgraphs with connected deletion sets

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