Security of Art Gallery (GRAPH)

[LinkXP]

Suppost we wanna put security cameras in an art gallery, and we have a graph were the points are the places and the lines between them means that they can see each other.

The problem is tu put the minimal amount of cameras.

[Zachm]

I'll try to translate this problem to graph theory notations:

A vertex cover of an undirected graph G = (V,E) is a subset V' of the vertices of the graph which contains at least one of the two endpoints of each edge.

The vertex cover problem is the optimization problem of finding a vertex cover of minimum size in a graph. Unfortunately for you, this problem is NP-complete, which means it is unlikely that there is an efficient algorithm to solve it.

If I were you, I would take a non-deterministic approach to deal with this problem.
A short google search came up with this link:
http://www.geocities.com/dharwadker/vertex_cover/

It includes algorithm explanation, complexity analysis and implementation (C++). Though it may take a little trial & error to find an algorithm adapted to your specific needs.

Good luck !

[LinkXP]

Thanks a lot.
But I have another problem, I cannot enter to the page, my server deny the acces to that site, I don´t know why.
Can you please download the page and the implementation of the algorithm for me???