Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
From MaRDI portal
Publication:3605506
DOI10.1007/978-3-642-00202-1_26zbMath1211.68465OpenAlexW1757816407WikidataQ57359830 ScholiaQ57359830MaRDI QIDQ3605506
Frances A. Rosamond, Michael Dom, Michael R. Fellows
Publication date: 24 February 2009
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-00202-1_26
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Approximation algorithms for orthogonal line centers, Fixed-parameter tractability and lower bounds for stabbing problems, On the parameterized complexity of some optimization problems related to multiple-interval graphs, Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization, Partial multicovering and the \(d\)-consecutive ones property, Approximation algorithms for orthogonal line centers, Geometric hitting set for segments of few orientations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Constant approximation algorithms for rectangle stabbing and related problems
- On the parameterized complexity of multiple-interval graph problems
- Approximation algorithms for hitting objects with straight lines
- Covering things with things
- 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
- The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
- Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
- Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems