I'm looking for an algorithm (not the code) to help solve a problem in python.

Given an undirected weighted graph with a number of nodes which represent military bases, lets say A, B, C and D. Each node has a weighted edge for the distance from one base to another miles.

A lookout tower can see in all directions for 15 miles. We want to place the smallest number lookout towers at the bases that gives full coverage from the lookout towers.

What would be the algorithm to find the smallest subset?

CodePudding user response：

Remove edges whose weight is larger than 15 miles, and keep edges whose weight is lower than 15 miles.

Now your problem is exactly the dominating set problem on the new graph.

In python, the graph library networkx offers two functions about dominating sets:

• networkx.dominating_set finds a dominating set of a given graph, but does not guarantee that this dominating set is the smallest;
• networkx.is_dominating_set checks that a given set of vertices is indeed a dominating set.