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

DOI10.1016/j.jcss.2019.05.001zbMath1425.68309OpenAlexW2947622378MaRDI QIDQ2316936

M. S. Ramanujan, Eduard Eiben, Danny Hermelin

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

parameterized complexitykernelizationvertex 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)

Related Items

On the lossy kernelization for connected treedepth deletion set, \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Tight approximation bounds for dominating set on graphs of bounded arboricity
• Kernelization – Preprocessing with a Guarantee
• Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
• (Meta) Kernelization
• Intersection Theorems for Systems of Sets
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Polynomial-time data reduction for dominating set
• Kernelization and Sparseness: the case of Dominating Set
• Kernelization Lower Bounds Through Colors and IDs
• Lossy kernelization
• Steiner Tree Approximation via Iterative Randomized Rounding
• Parameterized Algorithms
• The steiner problem in graphs