Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Wong, K.Y. Michael; Saad, David (2008)
Languages: English
Types: Article
Subjects: Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity, Condensed Matter - Disordered Systems and Neural Networks
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] D. Sherrington and S. Kirkpatrick, Phys. Rev. Lett. 35, 1792 (1975).
    • [2] S. Kirkpatrick and D. Sherrington, Phys. Rev. B 17, 4384 (1978).
    • [3] H. Nishimori, Statistical Physics of Spin Glasses and Information Processing, OUP UK (2001)
    • [4] S. F. Edwards and P. W. Anderson, J. Phys. F 5, 965 (1975).
    • [5] M. M´ezard, G. Parisi, and M. Virasoro, Spin Glass Theory and Beyond, World Scientific, Singapore (1987)
    • [6] Y. Fu and P. W. Anderson, J. Phys. A 19, 1605 (1986).
    • [7] M. M´ezard and G. Parisi, J. Physique 47, 1285 (1986).
    • [8] S. Kirkpatrick and B. Selman, Science 264, 1297 (1994).
    • [9] R. Mulet, A, Pagnani, M. Weigt, and R. Zecchina, Phys. Rev. Lett. 89, 268701 (2002).
    • [10] T. R. Jensen and B. Toft, Graph Coloring Problems (Wiley Interscience, 1995).
    • [11] M. R. Garey and D. S. Johnson, Computers and Intractability (Freeman, 1979).
    • [12] A. Braunstein, R. Mulet, A. Pagnani, M. Weigt, and R. Zecchina, Phys. Rev. E 68, 036702 (2003).
    • [13] J. van Mourik and D. Saad, Phys. Rev. E, 66, 056120 (2002).
    • [14] M. M´ezard, M. Palassini, and O. Rivoire, Phys. Rev. Lett. 95, 200202 (2005).
    • [15] R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Nature 400, 133 (1999).
    • [16] F. Krzakala and A. Pagnani, Phys. Rev. E 70, 046705 (2004).
    • [17] F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborov´a, Proc. Natl. Acad. Sci. U. S. A. 104, 10318 (2007).
    • [18] L. Zdeborov´a and F. Krzakala, Phys. Rev. E 76, 031131 (2007).
    • [19] F. Krzakala and L. Zdeborov´a, Europhys. lett. 81, 57005 (2008).
    • [20] B. J. Frey, Graphical Models for Machine Learning and Digital Communication (MIT Press, Cambridge, MA, 1998).
    • [21] M. M´ezard, G. Parisi, and R. Zecchina, Science 297, 812 (2002).
    • [22] S. T. McCormick, Math. Programming 26, 153 (1983).
    • [23] J. Kubiatowicz, D. Bindel, Y. Chen, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells and B. Zhao, OceanStore: An Extremely Wide-Area Storage System, U. C. Berkeley Technical Report No. UCB//CSD-00-1102 (1999).
    • [24] S Bounkong, J van Mourik and D Saad, Phys. Rev. E 74, 057101 (2006).
    • [25] A. Jiang and J. Bruck, Proc. IEEE Symposium on Information Theory, 381 (2002).
    • [26] K. Y. M. Wong and D. Saad, Phys. Rev. E 74, 010104 (2006).
    • [27] K. Y. M. Wong and D. Saad, Phys. Rev. E 76, 011115 (2007).
    • [28] D. J. Gross, I. Kanter, and H. Sompolinsky, Phys. Rev. Lett. 55, 304 (1985).
    • [29] O. Rivoire, G. Biroli, O. C. Martin, and M. M´ezard, Eur. Phys. J. B 37, 55 (2004).
    • [30] M. M´ezard and G. Parisi, Eur. Phys. J. B 20, 217 (2001).
    • [31] R. Monasson and R. Zecchina, Phys. Rev. E 56, 1357 (1997).
    • [32] K. Y. M. Wong, D. Sherrington, P. Mottishaw, R. Dewar, and C. de Dominicis, J. Phys. A 21, L99 (1988).
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article