next up previous
Next: Approximation Algorithms Up: NON DETERMINISTIC ALGORITHM Previous: Cook's Theorem

Restriction of NPC Problems

eg. coloring

2-coloring tex2html_wrap_inline278 P
3-coloring tex2html_wrap_inline278 NPC
coloring of planar graph using 4 colors takes linear time.

3-coloring of planar graphs is NPC


Sushil Prasad
Thu May 13 13:03:52 EDT 1999