Phys. Rev. E 68, 036702 (2003) [15 pages]Polynomial iterative algorithms for coloring and analyzing random graphsReceived 24 April 2003; published 3 September 2003 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 with a one-step replica-symmetry breaking approximation the precise value of the critical average connectivity cq. Moreover, we show that below cq there exists a clustering phase c∈[cd,cq] in which ground states spontaneously divide into an exponential number of clusters. Furthermore, we extended our considerations to the case of single instances showing consistent results. This leads us to propose a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region, i.e., when c∈[cd,cq]. © 2003 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevE.68.036702
DOI:
10.1103/PhysRevE.68.036702
PACS:
02.70.-c, 89.20.Ff, 75.10.Nr, 05.70.Fh
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.