Colouring random graphs and maximising local diversity

Details Colouring random graphs and maximising local diversity Colouring random graphs and maximising local diversity

2005-07-25

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

Physics

Condensed Matter

Statistical Mechanics

10 pages, 10 figures

Scientific paper

10.1103/PhysRevE.74.057101

We study a variation of the graph colouring problem on random graphs of finite average connectivity. Given the number of colours, we aim to maximise the number of different colours at neighbouring vertices (i.e. one edge distance) of any vertex. Two efficient algorithms, belief propagation and Walksat are adapted to carry out this task. We present experimental results based on two types of random graphs for different system sizes and identify the critical value of the connectivity for the algorithms to find a perfect solution. The problem and the suggested algorithms have practical relevance since various applications, such as distributed storage, can be mapped onto this problem.

Affiliated with

Also associated with

No associations

Rating

Colouring random graphs and maximising local diversity 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 Colouring random graphs and maximising local diversity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Colouring random graphs and maximising local diversity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-52980