canonical problems list

Question

Does anyone known of a a good reference for canonical CS problems?

I'm thinking of things like "the sorting problem", "the bin packing problem", "the travailing salesman problem" and what not.

edit: websites preferred

Answer 1

You can probably find the best in an algorithms textbook like Introduction to Algorithms. Though I've never read that particular book, it's quite renowned for being thorough and would probably contain most of the problems you're likely to encounter.

Answer 2

"Computers and Intractability: A guide to the theory of NP-Completeness" by Garey and Johnson is a great reference for this sort of thing, although the "solved" problems (in P) are obviously not given much attention in the book.

I'm not aware of any good on-line resources, but Karp's seminal paper Reducibility among Combinatorial Problems (1972) on reductions and complexity is probably the "canonical" reference for Hard Problems.