AN OPTIMAL ALGORITHM FOR SOLVING THE SEARCHLIGHT GUARDING PROBLEM ON WEIGHTED TREES

In this paper, we propose a new graph problem on a connected weighted undirected graph, called the searchlight guarding problem. Consider th at there is a fugitive who moves along the edges of a graph at any spe ed. We want to place a set of searchlights at vertices to search the e dges 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 on e set of searchlights with the minimum building cost, then find the on e with the minimum searching time, that is, where the time slot needed to capture the fugitive is minimum. We first prove that the problem i s NP-hard on weighted bipartite graphs. Then an O(n) time optimal algo rithm is designed to solve the problem on weighted trees, where n is t he 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 searc hlights with the minimum guarding cost and assign the searching direct ions of all edges by the dynamic programming strategy. In the second p hase, the searched time slots of each edge are determined. Both phases take linear time.