On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
From MaRDI portal
Publication:2316936
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Related Items (2)
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
This page was built for publication: On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
