We have chosen to structure the problems in the same way as Garey and Johnson did [6], that is systematically in twelve categories according to subject matter. The first five categories are divided into subcategories. The following table shows how many problems there are in each category in the August 1998 version of the compendium, compared to how many there are in [6].
Code  Name of category  Number of problems in  
G&J [6]  compendium  
GT  Graph theory  65  55 
ND  Network design  51  65 
SP  Sets and partitions  21  14 
SR  Storage and retrieval  36  10 
SS  Sequencing and scheduling  22  20 
MP  Mathematical programming  13  17 
AN  Algebra and number theory  18  1 
GP  Games and puzzles  15  2 
LO  Logic  19  13 
AL  Automata and language theory  21  5 
PO  Program optimization  10  2 
MS  Miscellaneous  19  17 
For many categories the numbers are about the same. This might be surprising considering that only some of the NPcomplete problems in [6] have corresponding optimization problems. The explanation is of course that several new NPcomplete problems have been studied since 1979: an updated list of NPcomplete problems would be much larger than the original one.
It is interesting that, in some categories, there are much fewer problems in the compendium than in [6]. The reason could either be that there are only a few optimization problems in these categories or that no approximability results have been shown for the optimization problems in these classes. The latter case suggests that more research is needed for these categories.
The current version of the compendium thus contains more than 200 problems. However, under the same basic problem, several variations are also included. A typical entry consists of eight parts: the first four parts are mandatory while the rest are optional.
The following is an example of what an entry looks like.
GT7. MINIMUM EDGE COLORING
