DPG Phi
Verhandlungen
Verhandlungen
DPG

Dresden 2003 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

DY: Dynamik und Statistische Physik

DY 51: Statistical physics (general) I

DY 51.3: Talk

Friday, March 28, 2003, 10:45–11:00, G\"OR/229

Coloring random graphs — •Martin Weigt1, Roberto Mulet2, Andrea Pagnani3, and Riccardo Zecchina41Institut für Theoretische Physik, Uni Göttingen, Bunsenstr. 9, 37073 Göttingen — 2University of Havana, Cuba — 3Universita di Roma “La Sapienza”, Italy — 4ICTP Trieste, Italy

We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on q, we find the precise value of the critical average connectivity cq. Moreover, we show that below cq there exist a clustering phase c∈ [cd,cq] in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms.

100% | Mobile Layout | Deutsche Version | Contact/Imprint/Privacy
DPG-Physik > DPG-Verhandlungen > 2003 > Dresden