Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

They didn't really explain why graph coloring can be done quickly in this case. I'm not familiar with graph coloring theory, but I know the general graph coloring problems are NP-complete. I'm guessing the reason you can use a greedy algorithm to get a decent coloring quickly is because you know the graph is planar, and because you don't actually care about getting a minimal coloring.


Coloring a graph is trivial, just give every node its own color.

The NP-complete problems are for finding the optimal number of colors, or determining if the graph can be colored using a set small number of colors.

Erin's solution aims for a small number of colors, but doesn't try to be the optimal number.


Probably. It's like: TSP is really really easy if you know your input is N vertices with N-1 edges forming a line.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: