home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / compiler / 1840 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  1.3 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!spdcc!iecc!compilers-sender
  2. From: kuzemcha@tartan.com
  3. Newsgroups: comp.compilers
  4. Subject: Re: Graph Coloring Problem
  5. Keywords: theory, books
  6. Message-ID: <92-11-031@comp.compilers>
  7. Date: 6 Nov 92 17:54:53 GMT
  8. Article-I.D.: comp.92-11-031
  9. References: <92-10-093@comp.compilers> <92-10-109@comp.compilers>
  10. Sender: compilers-sender@iecc.cambridge.ma.us
  11. Reply-To: kuzemcha@tartan.com
  12. Organization: Compilers Central
  13. Lines: 27
  14. Approved: compilers@iecc.cambridge.ma.us
  15.  
  16. Richter@lrz.lrz-muenchen.dbp.de writes:
  17. >Anyhow, the general problem is NP-complete and you should not search for
  18. >optimal solutions. For good approximations, first study the literature.
  19. >Sorry, I have no references at hand.
  20.  
  21. One good text is:
  22.     "Computers and Intractability -
  23.     A Guide to the Theory of NP-Completeness"
  24.  
  25.       Michael R. Garey  / David S. Johnson
  26.  
  27.     published by: W.H. Freeman and Co.,  New York
  28.     ISBN 0-7167-1045-5
  29.  
  30. This book lists over 300 NP-Complete problems, giving references to the
  31. original transformation proofs.  Of course, graph coloring problems are
  32. covered.
  33.  
  34. There is also a section on bounding the performance of approximation
  35. algorithms, although no particular algorithms are given.
  36.  
  37.  
  38. Regards,
  39. Ed Kuzemchak
  40. -- 
  41. Send compilers articles to compilers@iecc.cambridge.ma.us or
  42. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  43.