Random sampling of colourings of sparse random graphs with a constant number of colours

Details Random sampling of colourings of sparse random graphs with a constant number of colours Random sampling of colourings of sparse random graphs with a constant number of colours

2008-04-15

arxiv.org/abs/0804.2343v1

Computer Science

Discrete Mathematics

30 pages 0 figures, uses fullpage.sty

Scientific paper

10.1016/j.tcs.2008.05.008

In this work we present a simple and efficient algorithm which, with high probability, provides an almost uniform sample from the set of proper k-colourings on an instance of a sparse random graph G(n,d/n), where k=k(d) is a sufficiently large constant. Our algorithm is not based on the Markov Chain Monte Carlo method (M.C.M.C.). Instead, we provide a novel proof of correctness of our Algorithm that is based on interesting "spatial mixing" properties of colourings of G(n,d/n). Our result improves upon previous results (based on M.C.M.C.) that required a number of colours growing unboundedly with n.

Affiliated with

Also associated with

No associations

Rating

Random sampling of colourings of sparse random graphs with a constant number of colours 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 Random sampling of colourings of sparse random graphs with a constant number of colours, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random sampling of colourings of sparse random graphs with a constant number of colours will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-653070