An Approximation Algorithm for Clarity Edge Covering Problem

Clarity edge covering problem is a version of art gallery problem. In this problem the goal is finding the minimum number of guards which covers all edges. Here, meaning of visibility is different from art gallery problem and it is restricted. In this paper, a logarithmic approximation algorithm is presented for vertex guard version. In art gallery problem, one should find the minimum number of guards to patrol interior of a polygon. The guards may be placed inside the polygon or on the boundary, and may be stationary or mobile.

Provided by: Islamic Azad University Topic: Software Date Added: Apr 2012 Format: PDF

Find By Topic