These lecture notes are based on a series of lectures which I gave at the
Advanced Research Institute of Discrete Applied Mathematics (ARIDAM
VI) in June 1991.
The lectures were addressed to an audience of discrete mathematicians
and computer scientists. I have tried to make the material understandable
to both groups; the result is that there are introductions to topics such as
the complexity of enumeration, knots, the Whitney/Tutte polynomials and
various models of statistical physics.
The main thrust throughout is towards algorithms, applications and the
interrelationship among seemingly diverse problem areas. In many cases I
have only given sketches of the main ideas rather than full proofs. However, I
have tried to give detailed references. I have assumed some familiarity with
the basic concepts of computational complexity and combinatorics, but I
have aimed to define anything nonstandard when it is first encountered.
My notation in both cases corresponds to standard usage, such as Garey
and Johnson (1979) and Bollobas (1979).
Since the lectures I have rewritten the notes to incorporate some of the
new developments but the basic material is the essence of what was
presented. Much of the work was done when I held a John von Neumann
Professorship at the University of Bonn. I am very grateful for the
opportunity this offered, and to my friends at the Forschungsinstitut fur Diskrete
Mathematik, where the facilities and atmosphere make it such a stimulating
place to visit.