2 ms·
Not much faster. Any k-coloring algorithm of complexity F(n) can be used to create a chromatic number algorithm of complexity lg(N)F(N) simply by bisecting on N
by drivebyhooting 2mo ago
Not much faster.
Any k-coloring algorithm of complexity F(n) can be used to create a chromatic number algorithm of complexity lg(N)F(N) simply by bisecting on N.
- emil-lp 2mo agoA small tip: if you want to do this trick, with an exponential F, you probably want a linear search rather than a binary search. If your k << N then F(N/2) is going to eat up all of the running time of ΣF(i).
- yablak 2mo agoIs it faster to start by doubling?
- emil-lp 2mo agoIt depends on F, but usually, if F is like 2^n, then a single F(i) for a too large i, is slower than computing F(j) for all j < i. This is illustrated by the fact that there are more leaves in a complete binary tree than all the other nodes summed.