Paper Info
Title
From Neel to NPC: Colouring Small Worlds
Abstract
this paper are colourable using 3colours. (In physics the repeating pattern of alternatingcolours used for this is called a Neel state.)The hardness of colouring small-world graphshas previously been investigated by Walsh [14],who used the original linear model of Waltz andStrogatz. In addition to studying some otherconstraint satisfaction problems on small worldgraphs, Walsh showed that the cost to prove that asmall world graph is colourable has an "easy-hardeasy" behaviour as a...
Year
Venue
Keywords
2001
Clinical Orthopaedics and Related Research
linear model,statistical mechanics,computational complexity
Field
DocType
Volume
Discrete mathematics,Graph,Combinatorics,Heuristic,Random graph,Crossover,Small worlds,Coordination number,Lattice (order),Scheduling (computing),Mathematics
Journal
cs.CC/0107
Citations 
PageRank 
References 
1
5.30
3
Authors
1
Name
Order
Citations
PageRank
Pontus Svenson114922.31