It's still a beautiful book. It naturally falls open to Depth-First Search, and to Maximum Flow in a Network. I wonder what I was working on, in those long ago days?

This book is not for the faint of heart. There are no easy code snippets, nor elegant proofs with example algorithms. It earned a place in my permanent library, long ago. ( )

Indeholder "Preface", "1. Paths in Graphs", " 1.1 Introduction to Graph Theory", " 1.2 Computer Representation of Graphs", " 1.3 Euler Graphs", " 1.4 De Bruijn Sequences", " 1.5 Shortest-Path Algorithms", " Problems", " References", "2. Trees", " 2.1 Tree Definitions", " 2.2 Minimum Spanning Tree", " 2.3 Cayley's Theorem", " 2.4 Directed Tree Definitions", " 2.5 The Infinity Lemma", " 2.6 The number of spanning trees", " 2.7 Optimum branchings and directed spanning trees", " 2.8 Directed trees and Euler circuits", " Problems", " References", "3. Depth-First Search", " 3.1 DFS of undirected graphs", " 3.2 Algorithm for nonseparable components", " 3.3 DFS on digraphs", " 3.4 Algorithm for strongly-connected components", " Problems", " References", "4. Ordered Trees", " 4.1 Uniquely decipherable codes", " 4.2 Positional Trees and Huffman's Optimization Problem", " 4.3 Application of the Huffman Tree to Sort-by-Merge Techniques", " 4.4 Catalan Numbers", " Problems", " References", "5. Maximum Flow in a Network", " 5.1 The Ford and Fulkerson algorithm", " 5.2 The Dinic algorithm", " 5.3 Networks with upper and lower bounds", " Problems", " References", "6. Applications of Network Flow Techniques", " 6.1 Zero-one network flow", " 6.2 Vertex connectivity of graphs", " 6.3 Connectivity of digraphs and edge connectivity", " 6.4 Maximum-matching in bipartite graphs", " 6.5 Two problems on PERT-digraphs", " Problems", " References", "7. Planar Graphs", " 7.1 Bridges and Kuratowski's theorem", " 7.2 Equivalence", " 7.3 Euler's theorem", " 7.4 Duality", " Problems", " References", "8. Testing Graph Planarity", " 8.1 Introduction", " 8.2 The Path Addition Algorithm of Hopcroft and Tarjan", " 8.3 Computing an st-Numbering", " 8.4 The vertex addition algorithm of Lempel, Even, and Cederbaum", " Problems", " References", "9. The Theory of NP-completeness", " 9.1 Introduction", " 9.2 The NP class of decision problems", " 9.3 NP-complete problems and Cook's theorem", " 9.4 Three combinatorial problems which are NPC", " Problems", " References", "10. NP-complete graph problems", " 10.1 Clique, independent set and vertex cover", " 10.2 Hamilton paths and circuits", " 10.3 Coloring of graphs", " 10.4 Feedback sets in digraphs", " 10.5 Steiner tree", " 10.6 Maximum cut", " 10.7 Linear arrangement", " 10.8 Multicommodity integral flow", " Problems", " References", "Index".

Lærebog som blev brugt til et kursus, jeg engang fulgte med Sven Skyum som lærer. Sammen med Peter Hillingsøe lavede jeg et program til at finde maximalt flow i en vægtet graf vha MPM algoritmen, som er beskrevet ganske dårligt i denne bog på side 101, men det lærte vi meget af. ( )

A great book that was a text in one of the most enjoyable courses I ever took. Believe it or not, I still refer to it! ( )