开发者

Is there any well-known NP-complete problem that I can reduce a 'node placement' problem to?

开发者 https://www.devze.com 2023-04-10 14:18 出处:网络
I have the following NP-complete problem: Given: a set of locations in a N × N field, a set of m nodes, and

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

精彩评论

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

关注公众号