|
by Eric Lippert via Fabulous Adventures In Coding on 7/22/2010 1:54:00 PM
OK, we've got our basic data structures in place.
Graph colouring is a very well-studied problem. It's known to be NP-complete for arbitrary graphs, so (assuming that P!=NP) we're not going to find an always-fast algorithm for colouring an arbitrary graph. However, for typical graphs that we encounter in the wild, the following simple algorithm is pretty good. Start by saying that every node can be every possible colour. Then:
1) Do you have a single possible colouring for every node in t
... [ read more ]
|
|
