Computer Science – Computational Complexity
Scientific paper
2001-07-11
Computer Science
Computational Complexity
4 pages, 6 figures
Scientific paper
In this note, we present results for the colouring problem on small world graphs created by rewiring square, triangular, and two kinds of cubic (with coordination numbers 5 and 6) lattices. As the rewiring parameter p tends to 1, we find the expected crossover to the behaviour of random graphs with corresponding connectivity. However, for the cubic lattices there is a region near p=0 for which the graphs are colourable. This could in principle be used as an additional heuristic for solving real world colouring or scheduling problems. Small worlds with connectivity 5 and p ~ 0.1 provide an interesting ensemble of graphs whose colourability is hard to determine. For square lattices, we get good data collapse plotting the fraction of colourable graphs against the rescaled parameter parameter $p N^{-\nu}$ with $\nu = 1.35$. No such collapse can be obtained for the data from lattices with coordination number 5 or 6.
No associations
LandOfFree
From Neel to NPC: Colouring Small Worlds 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 From Neel to NPC: Colouring Small Worlds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and From Neel to NPC: Colouring Small Worlds will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-537935