1.5D terrain guarding problem parameterized by guard range

详细信息    查看全文

• 作者：Farnoosh Khodakarami ^{f.khodakarami@aut.ac.ir} ; Farzad Didehvar ; ^{didehvar@aut.ac.ir} ; Ali Mohades ^{mohades@aut.ac.ir}
• 关键词：Parameterized complexity ; Dynamic programming ; Guarding ; 1.5D terrain
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：24 January 2017
• 年：2017
• 卷：661
• 期：Complete
• 页码：65-69
• 全文大小：240 K
• 卷排序：661

文摘

We introduce the “terrain guard range” as a new geometric parameter. Terrain guard range derived from the real world applications. We presents an algorithm to produce a solution to the 1.5D terrain guarding problem. Terrain guarding is fixed-parameter tractable respect to the terrain guard range.