开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜