Fri, 6 Nov 1992 17:54:53 GMT

Related articles |
---|

[3 earlier articles] |

Re: Graph Coloring Problem pat%frumious.uucp@uunet.ca (1992-10-28) |

Re: Graph Coloring Problem Richter@lrz.lrz-muenchen.dbp.de (1992-10-28) |

Re: Graph Coloring Problem cliffc@rice.edu (1992-10-28) |

Re: Graph Coloring Problem moss@cs.umass.edu (1992-10-28) |

Re: Graph Coloring Problem preston@cs.rice.edu (1992-10-30) |

Re: Graph Coloring Problem sgall+@CS.CMU.EDU (1992-10-31) |

Re: Graph Coloring Problem kuzemcha@tartan.com (1992-11-06) |

Newsgroups: | comp.compilers |

From: | kuzemcha@tartan.com |

Organization: | Compilers Central |

Date: | Fri, 6 Nov 1992 17:54:53 GMT |

Keywords: | theory, books |

References: | 92-10-093 92-10-109 |

Richter@lrz.lrz-muenchen.dbp.de writes:

*>Anyhow, the general problem is NP-complete and you should not search for*

*>optimal solutions. For good approximations, first study the literature.*

*>Sorry, I have no references at hand.*

One good text is:

"Computers and Intractability -

A Guide to the Theory of NP-Completeness"

Michael R. Garey / David S. Johnson

published by: W.H. Freeman and Co., New York

ISBN 0-7167-1045-5

This book lists over 300 NP-Complete problems, giving references to the

original transformation proofs. Of course, graph coloring problems are

covered.

There is also a section on bounding the performance of approximation

algorithms, although no particular algorithms are given.

Regards,

Ed Kuzemchak

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.