NP-hardness of the cluster minimization problem revisited

Details NP-hardness of the cluster minimization problem revisited NP-hardness of the cluster minimization problem revisited

2005-09-06

arxiv.org/abs/cs/0509016v1

J. Phys. A: Math. Gen. 38, 8487 (2005)

Computer Science

Computational Complexity

8 pages, 2 figures, accepted to J. Phys. A: Math. and Gen

Scientific paper

10.1088/0305-4470/38/40/001

The computational complexity of the "cluster minimization problem" is revisited [L. T. Wille and J. Vennik, J. Phys. A 18, L419 (1985)]. It is argued that the original NP-hardness proof does not apply to pairwise potentials of physical interest, such as those that depend on the geometric distance between the particles. A geometric analog of the original problem is formulated, and a new proof for such potentials is provided by polynomial time transformation from the independent set problem for unit disk graphs. Limitations of this formulation are pointed out, and new subproblems that bear more direct consequences to the numerical study of clusters are suggested.

Affiliated with

Also associated with

No associations

Rating

NP-hardness of the cluster minimization problem revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with NP-hardness of the cluster minimization problem revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and NP-hardness of the cluster minimization problem revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-375300