There are many question that pose a none obscure problem and ask for the "best" algorithm, whatever "best" means.

For example, Given a graph, decide if its edge connectivity is at least n/2 or not,

The normal process is to search the literature with every single name of the problem, and find a recent paper. Usually the "best" result will be the one of the references. A more recent approach is to ask the question here.

Are there websites specifically dedicated with information like this? A database of problems and list of algorithms with their complexities? I am imagining an OEIS for problems instead of integer sequences.

  • $\begingroup$ See this question, I think this should be closed as duplicate. $\endgroup$ – Kaveh Sep 6 '11 at 6:00
  • $\begingroup$ I was not aware of that post. The answers do indicate no satisfactory resource exists. This should be closed. $\endgroup$ – Chao Xu Sep 6 '11 at 6:20
  • $\begingroup$ I agree that this question is a duplicate in spirit. However, this question is amore general than the linked one; in title at least. Although this answer would answer this more general question, the other answers are specific to NP-hardness results and/or are discussions. Thus it would be a little awkward to close it as "exact duplicate", no? $\endgroup$ – Artem Kaznatcheev Sep 6 '11 at 6:41

There's an attempt to build such a resource. It's called the Complexity Garden and is "the botanical companion to the Complexity Zoo". Also see this meta discussion.


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.