Is there a list of known problems?
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)