Can I read Polynomial Iterative Algorithms for Coloring and Analyzing Random Graphs on EtoBox?

Polynomial Iterative Algorithms for Coloring and Analyzing Random Graphs by Braunstein, A.; Mulet, R.; Pagnani, A.; Weigt, M.; Zecchina, R. is a scholarly article available to read on EtoBox.

What is Polynomial Iterative Algorithms for Coloring and Analyzing Random Graphs about?

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 $c\in [c_d,c_q]$ 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 lead us to propose a new algorithm able to color in polynomial time random graphs in the hard but colorable region, i.e when $c\in [c_d,c_q]$.

Author

Braunstein, A.; Mulet, R.; Pagnani, A.; Weigt, M.; Zecchina, R.

Published

2003

Language

EN