Relaxation in graph coloring and satisfiability problems

Details Relaxation in graph coloring and satisfiability problems Relaxation in graph coloring and satisfiability problems

1998-10-13

arxiv.org/abs/cond-mat/9810144v2

Phys. Rev. E 59(4) 3983-3999 (1999)

Physics

Condensed Matter

Disordered Systems and Neural Networks

13 pages, 22 figures. Several changes to text, figures added, section on feromagnetic model moved to a separate publication. A

Scientific paper

10.1103/PhysRevE.59.3983

Using T=0 Monte Carlo simulation, we study the relaxation of graph coloring (K-COL) and satisfiability (K-SAT), two hard problems that have recently been shown to possess a phase transition in solvability as a parameter is varied. A change from exponentially fast to power law relaxation, and a transition to freezing behavior are found. These changes take place for smaller values of the parameter than the solvability transition. Results for the coloring problem for colorable and clustered graphs and for the fraction of persistent spins for satisfiability are also presented.

Affiliated with

Also associated with

No associations

Rating

Relaxation in graph coloring and satisfiability problems 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 Relaxation in graph coloring and satisfiability problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relaxation in graph coloring and satisfiability problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-619404