Ultrametricity Transition in the Graph Colouring Problem
Europhysics Letters (EPL)Published 1 February 1986
J. P. Bouchaud, Pierre Le Doussal
Citations12
SJR quartileQ2
SJR score0.48
SNIP0.59
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We study numerically the (planar) graph colouring problem with q colours. For q = 4, when a perfect colouring can be achieved, the solutions are scattered "randomly" (as far as triangle correlations are concerned) in configuration space. On the contrary, for q = 3, colouring is always imperfect, but the optimal solutions seem to organize themselves in an ultrametric way. This could illustrate rather well the role of frustration on the configuration space landscape. We discuss the importance of the distance chosen.
Keywords
Computer Science
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
Proceedings of the National Academy of SciencesNeural networks and physical systems with emergent collective computational abilities.
19,349 Citations1982J. J. Hopfield
A model of a system having a large number of simple equivalent components, based on aspects of neurobiology but readily adapted to integrated circuits, produces a content-addressable memory which correctly yields an entire memory from any subpart of sufficient size.
Bulletin of the American Mathematical SocietyEvery planar map is four colorable
1,121 Citations1976K. I. Appel, Wolfgang Haken
Journal de physiqueReplica symmetry breaking and the nature of the spin glass phase
435 Citations1984Marc Mézard, Giorgio Parisi +3 more
Physical Review LettersMean-field theory of the Potts glass
368 Citations1985David J. Gross, Ido Kanter +1 more
Randomly interacting p-state Potts spins may freeze into a Potts-glass phase in which the Potts symmetry is unbroken, on the average, and the mean-field theory of this phase transition is presented.
Journal de physiqueConfiguration space analysis of travelling salesman problems
233 Citations1985Scott Kirkpatrick, G. Toulouse
A random distance TSP as similar as possible to the idealized infinite-ranged model of spin glasses, and evidence for freezing due to frustration and for a hierarchical, ultrametric structure of configuration space is presented.
Journal de Physique LettresThree-dimensional Ising spin-glasses and mean-field theory
23 Citations1984Nicolas Sourlas