Name
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 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. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1103/PhysRevE.59.3983 | PHYSICAL REVIEW E |
Keywords | Field | DocType |
col,power law,monte carlo simulation,graph coloring,phase transition,satisfiability | Spins,Discrete mathematics,Graph,Combinatorics,Monte Carlo method,Phase transition,Satisfiability,Power law,Mathematics,Graph coloring,Coloring problem | Journal |
Volume | Issue | ISSN |
59 | 4 | 2470-0045 |
Citations | PageRank | References |
7 | 0.58 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pontus Svenson | 1 | 149 | 22.31 |
| Mats G. Nordahl | 2 | 172 | 43.97 |