Re: Coloring a graph with exact N colors

TOUATI Sid <touati@prism.uvsq.fr>
30 Sep 2005 02:05:39 -0400

          From comp.compilers
Related articles
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 touati@prism.uvsq.fr (TOUATI Sid) (2005-09-27)
Re: Coloring a graph with exact N colors nkavv@skiathos.physics.auth.gr (Uncle Noah) (2005-09-30)
Re: Coloring a graph with exact N colors touati@prism.uvsq.fr (TOUATI Sid) (2005-09-30)
| List of all articles for this month |
From: TOUATI Sid <touati@prism.uvsq.fr>
Newsgroups: comp.compilers
Date: 30 Sep 2005 02:05:39 -0400
Organization: Universite de Versailles Saint-Quentin-en-Yvelines
References: 05-09-084
Keywords: registers
Posted-Date: 30 Sep 2005 02:05:39 EDT

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...


S

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.