Minimizing Unsatisfaction in Colourful Neighbourhoods
arXiv:0704.3835 · doi:10.1088/1751-8113/41/32/324023
Abstract
Colouring sparse graphs under various restrictions is a theoretical problem of significant practical relevance. Here we consider the problem of maximizing the number of different colours available at the nodes and their neighbourhoods, given a predetermined number of colours. In the analytical framework of a tree approximation, carried out at both zero and finite temperatures, solutions obtained by population dynamics give rise to estimates of the threshold connectivity for the incomplete to complete transition, which are consistent with those of existing algorithms. The nature of the transition as well as the validity of the tree approximation are investigated.
28 pages, 12 figures, substantially revised with additional explanation
References in corpus (15)
- The Bethe lattice spin glass revisited
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Phase Transitions in the Coloring of Random Graphs
- Statistical mechanics of the random K-SAT model
- Coloring random graphs
- Glass models on Bethe lattices
- Polynomial iterative algorithms for coloring and analyzing random graphs
- Landscape of solutions in constraint satisfaction problems
- Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
- Potts Glass on Random Graphs
- Random Graph Coloring - a Statistical Physics Approach
- Equilibration through local information exchange in networks
- Inference and Optimization of Real Edges on Sparse Graphs - A Statistical Physics Perspective
- Limits on anomalous trilinear gauge couplings from WW->e+e-, WW->emu, and WW->mu+mu- events from p-pbar collisions at sqrt(s)=1.96 TeV
- Colouring random graphs and maximising local diversity
Cited by in corpus (6)
- Networking - A Statistical Physics Perspective
- Partition function loop series for a general graphical model: free energy corrections and message-passing equations
- Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example
- Coverage versus Supply Cost in Facility Location: Physics of Frustrated Spin Systems
- Palette-colouring: a belief-propagation approach
- Slow Spin Dynamics and Self-Sustained Clusters in Sparsely Connected Systems