4 ms·
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 colori
by openasocket 2y ago
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.
- deleted 2y ago[deleted]
- jvanderbot 2y agoProbably. It's like: TSP is really really easy if you know your input is N vertices with N-1 edges forming a line.
- jtolmar 2y agoColoring 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.