The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants

DOI10.1007/978-3-540-69311-6_30zbMath1143.68617OpenAlexW2116542451MaRDI QIDQ3507345

Michael Dom, Somnath Sikdar

Publication date: 19 June 2008

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69311-6_30

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (4)

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 ⋮ Parameterized Complexity of Stabbing Rectangles and Squares in the Plane

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the parameterized complexity of multiple-interval graph problems
• Approximation algorithms for hitting objects with straight lines
• Covering things with things
• Parametrized complexity theory.
• Station Location - Complexity and Approximation.
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Approximation Algorithms for Capacitated Rectangle Stabbing
• Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems

This page was built for publication: The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants