Shimon Even (1935–2004)

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.… (mehr)