Efficient algorithms for the conditional covering problem

详细信息    查看全文

• 作者：Robert Benkoczi ; Binay Bhattacharya ; Yuzhuang Hu ; Chien-Hsin Lin ; Qiaosheng Shi ; Biing-Feng Wang
• 关键词：Algorithms ; Graphs ; Covering location problems ; Conditional covering ; Dynamic programming
• 刊名：Information and Computation
• 出版年：2012
• 出版时间：October, 2012
• 年：2012
• 卷：219
• 期：Complete
• 页码：39-57
• 全文大小：570 K

文摘

We consider the conditional covering problem in an undirected network, in which each vertex represents a demand point that must be covered by a facility as well as a potential facility site. Each facility can cover all vertices within a given coverage radius, except the vertex at which the facility is located. The objective is to locate facilities to cover all vertices such that the total facility location cost is minimized. In this paper, new upper bounds are proposed for the conditional covering problem on paths, cycles, extended stars, and trees. In particular, we provide an -time algorithm for paths, an -time algorithm for cycles, an -time algorithm for extended stars, and an -time algorithm for trees. Our algorithms for paths, extended stars, and trees improve the previous upper bounds from , , and , respectively.