Parameterized complexity of \(d\)-hitting set with quotas
From MaRDI portal
Publication:831823
DOI10.1007/978-3-030-67731-2_21zbMath1490.68122OpenAlexW3125003100MaRDI QIDQ831823
Sagar Singh, Pallavi Jain, Sushmita Gupta, Aditya Petety
Publication date: 24 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-67731-2_21
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Solving min ones 2-SAT as fast as vertex cover
- A randomised approximation algorithm for the hitting set problem
- Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
- An efficient fixed-parameter algorithm for 3-hitting set
- A kernelization algorithm for \(d\)-hitting set
- Characterizing diagnoses and systems
- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
- Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
- Kernelization
- Tight Approximation Bounds for Maximum Multi-coverage
- Towards Work-Efficient Parallel Parameterized Algorithms
- Exact Algorithms via Monotone Local Search
- Parameterized Algorithms
- Conflict free version of covering problems on graphs: classical and parameterized
This page was built for publication: Parameterized complexity of \(d\)-hitting set with quotas