OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]openaire.eu

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Wong, K. Y. Michael; Saad, David (2007)
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

Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok