Parameterized Complexity of Stabbing Rectangles and Squares in the Plane

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

Mathematics Subject Classification ID

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