Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
From MaRDI portal
Publication:1679222
DOI10.1007/s00453-016-0216-xzbMath1380.68212arXiv1511.07642OpenAlexW2176388081MaRDI QIDQ1679222
Saket Saurabh, Sudeshna Kolay, Pradeesha Ashok
Publication date: 9 November 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.07642
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Infeasibility of instance compression and succinct PCPs for NP
- Graph minors. III. Planar tree-width
- Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Red-blue covering problems and the consecutive ones property
- On two techniques of combining branching and treewidth
- On problems without polynomial kernels
- Which problems have strongly exponential complexity?
- Geometric red-blue set cover for unit squares and related problems
- Covering things with things
- Parametrized complexity theory.
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Kernelization Lower Bounds Through Colors and IDs
- Point Line Cover
- Reducibility among Combinatorial Problems
- Algorithms – ESA 2005
This page was built for publication: Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
