6
$\begingroup$

When I was studying Comp Sci, we had Garey & Johnson as a course textbook, with a large collection of NP-Complete problems. But by that time you could also have a look at the Compendium of NP Optimization Problems, online.

However, it seems the 'Compendium' site has not seen any updates in several years. Is that indeed the case? Is there a more up-to-date compendium (perhaps in print) which accounts for further research and contains more problems in more domains?

$\endgroup$
4
$\begingroup$

I know of no compendium that is completely satisfactory in any regard. It seems to be too much of a thankless task maintaining these things, thus I suspect that broad answer to your question is, unfortunately, no.

However, there are several resources which, together, are at least a good start for any search.

In this case, Wikipedia is a fairly decent resource (I guess the contribution model helps overcome some of the problems with a single-curator approach, but you lose the consistency).

If you're interested in Parameterized Complexity, Marco Cesati began a compendium of problems, but like Kann, has (understandably) not kept up with the updates. There's also an online compendium, but it is less comprehensive.

A similar question was also asked on cstheory, attracting a couple of answers, one that caught my eye was the Encyclopedia of Algorithms. I cannot personally vouch for it, but it at least looks useful, or at least useful enough to convince a university library to buy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.