The Parameterized Complexity of Stabbing Rectangles

被引：0
作者：
Michael Dom
Michael R. Fellows
Frances A. Rosamond
Somnath Sikdar
机构：
[1] Friedrich-Schiller-Universität Jena,Institut für Informatik
[2] Charles Darwin University,School of Engineering and Information Technology
[3] RWTH Aachen University,Department of Computer Science
来源：
Algorithmica | 2012年 / 62卷
关键词：
Parameterized complexity; Fixed-parameter algorithms; Geometric covering problems; Whardness;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The NP-complete geometric covering problem Rectangle Stabbing is defined as follows: Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines in the plane, and a positive integer k, select at most k of the lines such that every rectangle is intersected by at least one of the selected lines.
引用
收藏
页码：564 / 594
页数：30
相关论文
共 71 条
[1]  
Abrahamson K.R.(1995)Fixed-parameter tractability and completeness IV: on completeness for W[ Ann. Pure Appl. Logic 73 235-276
[2]  
Downey R.G.(1998)] and PSPACE analogues ACM Comput. Surv. 30 412-458
[3]  
Fellows M.R.(1996)Efficient algorithms for geometric optimization Discrete Appl. Math. 71 23-40
[4]  
Agarwal P.K.(2005)On physical mapping and the consecutive ones property for sparse matrices Int. J. Comput. Geom. Appl. 15 575-590
[5]  
Sharir M.(2005)Separating points by axis-parallel lines Inf. Comput. 201 216-231
[6]  
Atkins J.E.(2007)Tight lower bounds for certain parameterized NP-hard problems Discrete Comput. Geom. 37 43-58
[7]  
Middendorf M.(2003)Improved approximation algorithms for geometric set cover Electron. Notes Theor. Comput. Sci. 78 209-222
[8]  
Călinescu G.(2008)Cutting up is hard to do: the parameterised complexity of ACM Trans. Algorithms 4 53-61
[9]  
Dumitrescu A.(2009)-Cut and related problems Theor. Comput. Sci. 410 549-568
[10]  
Karloff H.J.(1996)Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs Algorithmica 16 71-100
12345678