摘要
In this paper, we propose a new graph problem on a connected weighted undirected graph, called the searchlight guarding problem. Consider that there is a fugitive who moves along the edges of a graph at any speed. We want to place a set of searchlights at vertices to search the edges of the graph and capture the fugitive. Suppose that it costs some building cost to place a searchlight at some vertex. The searchlight guarding problem is to allocate a set S of searchlights such that the summation of the building costs is minimized. If there is more than one set of searchlights with the minimum building cost, then find the one with the minimum searching time, that is, where the time slot needed to capture the fugitive is minimum. We first prove that the problem is NP-hard on weighted bipartite graphs. Then an O(n) time optimal algorithm is designed to solve the problem on weighted trees, where n is the number of the vertices of the given weighted tree. The algorithm is divided into two phases: In the first phase, we find the set of searchlights with the minimum guarding cost and assign the searching directions of all edges by the dynamic programming strategy. In the second phase, the searched time slots of each edge are determined. Both phases take linear time. © 1995.