The parameterized complexity of stabbing rectangles
From MaRDI portal
Publication:2428672
DOI10.1007/s00453-010-9471-4zbMath1236.68083OpenAlexW2032054765WikidataQ57359642 ScholiaQ57359642MaRDI QIDQ2428672
Michael R. Fellows, Michael Dom, Somnath Sikdar, Frances A. Rosamond
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-010-9471-4
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and lower bounds for stabbing problems
- Orthogonal segment stabbing
- Constant approximation algorithms for rectangle stabbing and related problems
- Improved approximation algorithms for geometric set cover
- On the parameterized complexity of multiple-interval graph problems
- Approximation algorithms for hitting objects with straight lines
- Which problems have strongly exponential complexity?
- On the complexity of locating linear facilities in the plane
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
- Covering things with things
- Tight lower bounds for certain parameterized NP-hard problems
- Station Location - Complexity and Approximation.
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- SEPARATING POINTS BY AXIS-PARALLEL LINES
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing
- ON PIERCING SETS OF AXIS-PARALLEL RECTANGLES AND RINGS
- Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
- Interval routing schemes
- On Physical Mapping and the consecutive ones property for sparse matrices
This page was built for publication: The parameterized complexity of stabbing rectangles
