Is there any well-known NP-complete problem that I can reduce a 'node placement' problem to?
I have the following NP-complete problem:
Given:
- a set of locations in a N × N field,
- a set of m nodes, and
- a connectivity graph of the nodes (i.e. an undirected graph whose edges represent every pair of nodes in contact with each other), and
- contact range R (in the same length unit as the N × N field),
find a placement of the nodes in the field respecting the connectivity graph (i.e. place nodes such that any pair in contact is nearer than R and any pair not in contact is farther than R), or show that such placement does not exist.
Is the a well-known NP-complete problem that this problem can be reduced to?
(Also an optimization version of the problem can开发者_高级运维 be considered, i.e. to find the most optimal placement)
Set cover sounds alot like this problem. In fact, it may be almost precisely this problem. Even better: it has an approximation algorithm guaranteed to be within O(log n) of the optimal solution.
精彩评论