30 Sep 2005 02:05:39 -0400

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

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 |

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.