XII Preface solution as efficiently as possible. Most of the problems we treat have a good algorithmic solution, but we also show how even difficult problems can be treated (for example by approximation algorithms or complete enumeration) using a particular hard problem (namely the famous travelling salesman problem) as an example. Such techniques are interesting even for problems where it is possible to find an exact solution because they may decrease the amount of calculations needed considerably. In order to be able to judge the quality of algorithms and the degree of difficulty of problems, we introduce the basic ideas of complexity theory (in an informal way) and explain one of the main open problems of modern mathematics (namely the question P= NP?). In the first chapters of the book, we will present algorithms in a rather detailed manner but turn to a more concise presentation in later parts. We decided not to include any explicit programs in this book; it should not be too difficult for a reader who is used to writing programs to transfer the given algorithms. Giving programs in any fixed programming language would have meant that the book is likely to be obsolete within a short time; moreover, explicit programs would have obscured the mathematical background of the algorithms. However, we use a structured way of presentation for our algorithms, including special commands based on PASCAL (a rather usual approach). The book contains a lot of exercises and, in the appendix, the solutions or hints for finding the solution. As in any other discipline, combinatorial optimization can be learned best by really working with the material; this is true in particular for understanding the algorithms. Therefore, we urge the reader to work on the exercises seriously (and do the mere calculations as well). The present book is a translation of a revised version of the third edition of my German text book Graphen, Netzwerke und Algorithmen. The translation and the typesetting was done by Dr. Tilla Schade with my collaboration. The text is based on two courses I gave in the winter term 1984/85 and in the summer term 1985 at the Justus-Liebig-University in Gießen. As the first edition of the book which appeared in 1987 was received quite well, a second edition became necessary in 1990. This second edition was only slightly changed (there were only a few corrections and some additions made, including a further appendix and a number of new references), because it appeared a relatively short time after the first edition. The third edition, however, was completely revised and newly typeset. Besides several corrections and rearrangements, some larger supplements were added and the references brought up to date. The lectures and seminars concerning combinatorial optimization and graph theory that I continued to give regularly (first at the University of Gießen, then since the summer term 1993 at the University of Augsburg) were very helpful here. I used the text presented here repeatedly; I also took it as the basis for a workshop for high school students organized by the Verein Bildung und Begabung. This workshop showed that the subjects treated in this book are accessible even to high school students; if motivated sufficiently, they approach the problems with great interest. Moreover, the German edition has been used regularly at various other universities.