Precise polynomial heuristic for an NP-complete problem

Details Precise polynomial heuristic for an NP-complete problem Precise polynomial heuristic for an NP-complete problem

2003-09-12

arxiv.org/abs/cond-mat/0309324v1

Physics

Condensed Matter

Statistical Mechanics

Scientific paper

We introduce a simple, efficient and precise polynomial heuristic for a key NP complete problem, minimum vertex cover. Our method is iterative and operates in probability space. Once a stable probability solution is found we find the true combinatorial solution from the probabilities. For system sizes which are amenable to exact solution by conventional means, we find a correct minimum vertex cover for all cases which we have tested, which include random graphs and diluted triangular lattices of up to 100 sites. We present precise data for minimum vertex cover on graphs of up to 50,000 sites. Extensions of the method to hard core lattices gases and other NP problems are discussed.

Affiliated with

Also associated with

No associations

Rating

Precise polynomial heuristic for an NP-complete problem 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 Precise polynomial heuristic for an NP-complete problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Precise polynomial heuristic for an NP-complete problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-230288