|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Coloring random graphs | | R. Mulet
; A. Pagnani
; M. Weigt
; R. Zecchina
; | | Date: |
23 Aug 2002 | | Journal: | Phys. Rev. Lett. 89, 268701 (2002) | | Subject: | Statistical Mechanics; Disordered Systems and Neural Networks; Computational Complexity | cond-mat.stat-mech cond-mat.dis-nn cs.CC | | Abstract: | 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 $c_q$. Moreover, we show that below $c_q$ there exist a clustering phase $cin [c_d,c_q]$ 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. | | Source: | arXiv, cond-mat/0208460 | | Other source: | [GID 389669] pmid12484862 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER