Graphs, Networks and Algorithms.
David Keith Smith, D. Jungnickel · Journal of the Operational Research Society · 1999
Once again, the new edition has been thoroughly revised, even though the changes are less extensive than for the third edition.(Well, one does hope for some sort of convergence of the writing process.)In particular, I have again added some further material: more on NPcompleteness (especially on dominating sets), a section on the Gallai-Edmonds structure theory for matchings, and about a dozen additional exercises-as always, with solutions.Moreover, the section on the 1-factor theorem has been completely rewritten: it now presents a short direct proof for the more general Berge-Tutte formula.I have also used this opportunity to discuss several recent research developments and added quite a few references.Finally, smaller changes and corrections-mainly to typographical errors-have been made.As always, I am indebted to my students and assistants for their attention and interest.Special thanks are due to Dr. Matthias Tinkl who was in charge of the examples classes for a couple of lecture courses based on this text and also contributed several improved figures, and to one of our students, Alexander Müller, for his careful reading and helpful suggestions.