The parameterized complexity of stabbing rectangles

DOI10.1007/s00453-010-9471-4zbMath1236.68083WikidataQ57359642 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

zbMATH Keywords

fixed-parameter algorithms; parameterized complexity; geometric covering problems

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

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