# A compendium of NP optimization problems

Editors:
Pierluigi Crescenzi, piluc@dsi.unifi.it and Viggo Kann, viggo@nada.kth.se
Subeditors:
Magnús Halldórsson
Graph Theory: Covering and Partitioning, Subgraphs and Supergraphs, Sets and Partitions.
Marek Karpinski
Graph Theory: Vertex Ordering, Network Design: Cuts and Connectivity.
Gerhard Woeginger
Sequencing and Scheduling.

This is a copy of the April 1999 version of the on-line web version of the compendium that also appears in the appendix of the book. The on-line version is continuously updated, so check there for the latest results.

You can use web forms to report new problems, new results on existing problems, updates of references or errors.

There is a paper describing how the compendium is used.

- Introduction
  - NPO problems: definitions and preliminaries
  - Terminology for graph problems
  - Approximate algorithms and approximation classes
  - Completeness in approximation classes
  - A list of NPO problems
  - Improving the compendium
- Graph Theory
  - Covering and Partitioning
  - Subgraphs and Supergraphs
  - Vertex Ordering
  - Iso- and Other Morphisms
  - Miscellaneous
- Network Design
  - Spanning Trees
  - Cuts and Connectivity
  - Routing Problems
  - Flow Problems
  - Miscellaneous
- Sets and Partitions
  - Covering, Hitting, and Splitting
  - Weighted Set Problems
- Storage and Retrieval
  - Data Storage
  - Compression and Representation
  - Miscellaneous
- Sequencing and Scheduling
  - Sequencing on One Processor
  - Multiprocessor Scheduling
  - Shop Scheduling
  - Miscellaneous
- Mathematical Programming
- Algebra and Number Theory
  - Solvability of Equations
- Games and Puzzles
- Logic
  - Propositional Logic
  - Miscellaneous
- Automata and Language Theory
  - Automata Theory
  - Formal Languages
  - Miscellaneous
- Program Optimization
  - Code Generation
- Miscellaneous
- Bibliography
- Index
- About this document ...