Relaxation in graph coloring and satisfiability problems

Preprint
Publisher Website
Google Scholar
  • 13 October 1998
Abstract
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 transition from exponentially fast to power law relaxation is found. The transition occurs for a smaller value of the parameter than the solvability transition. The coloring problem for colorable and clustered graphs, and a ferromagnetic Potts model on a random graph are also studied.

This publication has 0 references indexed in Scilit: