Re: Graph Coloring Problem

kuzemcha@tartan.com
Fri, 6 Nov 1992 17:54:53 GMT

          From comp.compilers
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)
| List of all articles for this month |
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.