27 Sep 2005 09:50:19 -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: | 27 Sep 2005 09:50:19 -0400 |

Organization: | Universite de Versailles Saint-Quentin-en-Yvelines |

References: | 05-09-084 |

Keywords: | optimize, theory |

This is called q-coloring in graph theory (q=N in your message). The

complexity is not exponential as with optimal coloring, but the constant

of the complexity is high (=N!). In practice, N <= 12 is an observed limit.

S

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.