Parameterized complexity of geometric covering problems having conflicts
From MaRDI portal
Publication:5919304
DOI10.1007/s00453-019-00600-wzbMath1436.68145OpenAlexW2961406866WikidataQ127519379 ScholiaQ127519379MaRDI QIDQ5919304
Saket Saurabh, Venkatesh Raman, Fahad Panolan, Vibha Sahlot, Aritra Banik
Publication date: 16 January 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-019-00600-w
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Fréchet distance between a line and avatar point set
- Improved approximation algorithms for geometric set cover
- 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
- On two techniques of combining branching and treewidth
- A parameterized view on matroid optimization problems
- Forests, frames, and games: Algorithms for matroid sums and applications
- Selecting and covering colored points
- Almost optimal set covers in finite VC-dimension
- Bichromatic 2-center of pairs of points
- Covering things with things
- Parametrized complexity theory.
- Geometric Avatar Problems
- Guarding terrains via local search
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Deterministic Truncation of Linear Matroids
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Choice Is Hard
- Minimum-diameter covering problems
- Polynomial-time approximation schemes for packing and piercing fat objects
- Point Line Cover
- Lossy kernelization
- Reducibility among Combinatorial Problems
- How to Think About Algorithms
- Multiplying matrices faster than coppersmith-winograd
- Algorithms – ESA 2005
- Improved Bounds for the Union of Locally Fat Objects in the Plane
- Parameterized Algorithms
