Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

#1 2010-10-27 18:44:31

kadixt
Novice

Offline

k-Colorability Reduction

Hi everyone,

I'm having trouble reducing a k-Colorability problem to an Exact Cover problem (NP problems).
I've got an algorithm that can do it for k=2, but does anyone know of a way to reduce for k>=3?
I've searched far and wide on Google, Bing etc but can't find anything.

Would really appreciated any advice!!

Cheers,

Nelson

Board footer

Powered by FluxBB