On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
From MaRDI portal
Publication:2316936
DOI10.1016/j.jcss.2019.05.001zbMath1425.68309MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68W25: Approximation algorithms
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
