|Coloring a graph with exact N colors dot (tzuchienchiu <at> gmail <dot> com<tzuchien.chiu@gm) (2005-09-22)|
|Re: Coloring a graph with exact N colors firstname.lastname@example.org (TOUATI Sid) (2005-09-27)|
|Re: Coloring a graph with exact N colors email@example.com (Uncle Noah) (2005-09-30)|
|Re: Coloring a graph with exact N colors firstname.lastname@example.org (TOUATI Sid) (2005-09-30)|
|From:||TOUATI Sid <email@example.com>|
|Date:||30 Sep 2005 02:05:39 -0400|
|Organization:||Universite de Versailles Saint-Quentin-en-Yvelines|
This is called q-coloring is graph theory, where q is a constant (which
you call N in your message). computing a q-coloring of a graph given a
constant Q is a polynomial problem, but the constant of the complexity
is q!, which is exponential. With the actual machines, we observed that
Q<=12 is a limit for performing a q-coloring. So if you try to color
your graph with more than 12 colors, you would highly require many many
time and space...
Return to the
Search the comp.compilers archives again.