Polynomial iterative algorithms for coloring and analyzing random graphs

Details Polynomial iterative algorithms for coloring and analyzing random graphs Polynomial iterative algorithms for coloring and analyzing random graphs

2003-04-24

arxiv.org/abs/cond-mat/0304558v1

Phys. Rev. E 68, 036702 (2003)

Physics

Condensed Matter

Disordered Systems and Neural Networks

23 pages, 10 eps figures

Scientific paper

10.1103/PhysRevE.68.036702

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]$.

Affiliated with

Also associated with

No associations

Rating

Polynomial iterative algorithms for coloring and analyzing random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial iterative algorithms for coloring and analyzing random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial iterative algorithms for coloring and analyzing random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-519130