8
$\begingroup$

Is there a database of known problems with information about their complexity and algorithms, related problems, references etc that is available to us? [If not, can we make one? I know this is off topic, but it would be SO useful]

$\endgroup$
  • 2
    $\begingroup$ Usually I just go to Wikipedia - however, I think it would be a great idea to have a TCS Wiki, devoted entirely to topics in theoretical computer science. I'd definitely be interested in helping out with that, if someone was going to start one. $\endgroup$ – Gautam Kamath Jan 16 '11 at 5:20
  • 2
    $\begingroup$ (1) I am not sure about the decision that this is a duplicate of Major unsolved problems in theoretical computer science. I guess that the word “problem” in this question refers to a problem in complexity-theory sense, not to an open problem. (2) A compendium of NP optimization problems is a nice place to look at, but you are asking for something more general. (3) I doubt that such a wide-range list will be useful, but I am not really sure. $\endgroup$ – Tsuyoshi Ito Jan 16 '11 at 7:45
  • 2
    $\begingroup$ reopened. I still think the question is very vague, but that's just my opinion as one person. $\endgroup$ – Suresh Venkat Jan 16 '11 at 11:51
  • 1
    $\begingroup$ I think that the question in some sense can be very useful, since we could gather here links on databases with problems and results on them. What concerns scheduling theory, there is at least one such database:The scheduling zoo(lix.polytechnique.fr/~durr/query). Another well-known database concerning graphs is this:wwwteo.informatik.uni-rostock.de/isgci/index.html. Thus we could just compose the list with such databases as the answer to the above question. In this sense the question isn't a duplicate of any question on cstheory. $\endgroup$ – Oleksandr Bondarenko Jan 16 '11 at 12:13
  • 2
    $\begingroup$ There is also the "Complexity Garden", related to the Complexity Zoo but dealing specifically with problems rather than complexity classes. It is a very tiny database, though: qwiki.stanford.edu/index.php/Complexity_Garden $\endgroup$ – Ryan Williams Jan 16 '11 at 20:13
1
$\begingroup$

If you do not insist on a database, the Encyclopedia of algorithms By Ming-Yang Kao is very valuable reference. The above link is the entry for the minimum Bandwidth problem.

This is an encyclopedia of algorithms that sets out the solutions to important algorithmic problems. It aims to be a comprehensive collection and is designed to provide quick and easy access for both students and researchers.” (Kybernetes, Vol. 38 (1/2), 2009)

$\endgroup$
  • $\begingroup$ It looks good, but most useful is something I can have in electronic form and both search or skip through randomly. I'll have to get this, in any case. $\endgroup$ – Ritwik Bose Jan 16 '11 at 21:15
1
$\begingroup$

There is a large list of algorithms and data structures on the National Institute of Standards and Technology governmental website: http://xw2k.nist.gov/dads/

It's not complete and I don't know how new algorithms, problems, and data structures can be added, but it has a decently large list. Links to implementations of each description are included, if available.

There are also links to additional resources near the bottom of the page.

$\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.