Graphs, Algorithms, and Optimization
The authors decided to write a textbook that would introduce the realm of graph theory to computer science students. In many ways they have undoubtedly succeeded. Rigorously stated mathematical theorems and proofs continuously interlace with tables of programming codes formally describing the algorithms presented. Spice is added to the menu now and then by slight detours to the theory of NP-completeness and a few samples of polynomial reductions, a few more advanced techniques of proof exploiting linear algebra, and a slightly informal but illustrative exposition of embeddings of graphs on surfaces of higher genus. The topics covered include basic notions of degree sequences, trees, cycles and connectivity, all illustrated from an algorithmic point of view. Further topics include matchings and Hamilton cycles, network flows and Menger theorems, and graph colorings. The relatively slow pace of the introductory chapters becomes a bit faster towards the end of the textbook and in the end the final chapters face an ambitious task of introducing linear programming to the reader. It is hard to imagine that all the material could be covered in a single one-semester course but, if the lecturer invests just a little bit of effort in careful selection, this textbook can be used to teach a very nice course on computer science.