Enhanced descriptions from Syndetics:

Updated second edition presents algorithms for shortest paths, maximum flows, dynamic programming and backtracking. Also discussed are binary trees, heuristic and near optimums, matrix multiplication, and NP-complete problems. New to this edition: how to mix known algorithms and create new ones. Features 153 black-and-white illustrations and 23 tables. Exercises, with answers at the ends of chapters.

Table of contents provided by Syndetics

• Chapter 1 Shortest Paths
• 1.1 Graph terminology
• 1.2 Shortest path
• 1.3 Multiterminal shortest paths
• 1.4 Decomposition algorithm
• 1.5 Acyclic network
• 1.6 Shortest paths in a general network
• 1.7 Minimum spanning tree
• 1.8 Breadth-first-search and depth-first-search
• Chapter 2 Maximum flows
• 2.1 Maximum flow
• 2.2 Algorithms for max flows
• 2.2.1 Ford and Fulkerson
• 2.2.2 Karzanov's algorithm
• 2.2.3 MPM algorithms
• 2.2.4 Analysis of algorithms
• 2.3 Multi-terminal maximum flows
• 2.3.1 Realization
• 2.3.2 Analysis
• 2.3.3 Synthesis
• 2.3.4 Multi-commodity flows
• 2.4 Minimum cost flows
• 2.5 Applications
• 2.5.1 Sets of distinct representatives
• 2.5.2 PERT
• 2.5.3 Optimum communication spanning tree
• Chapter 3 Dynamic programming
• 3.1 Introduction
• 3.2 Knapsack problem
• 3.3 Two-dimensional knapsack problem
• 3.4 Minimum-cost alphabetic tree
• 3.5 Summary
• Chapter 4 Backtracking
• 4.1 Introduction
• 4.2 Estimating the efficiency of backtracking
• 4.3 Branch and bound
• 4.4 Game-tree
• Chapter 5 Binary tree
• 5.1 Introduction
• 5.2 Huffman's tree
• 5.3 Alphabetic tree
• 5.4 Hu-Tucker algorithm
• 5.5 Feasibility and optimality
• 5.6 Garsia and Wachs' algorithm
• 5.7 Regular cost function
• 5.8 T-ary tree and other results
• Chapter 6 Heuristic and near optimum
• 6.1 Greedy algorithm
• 6.2 Bin-packing
• 6.3 Job-scheduling
• 6.4 Job-scheduling (tree-constraints)
• Chapter 7 Matrix multiplication
• 7.1 Strassen's matrix multiplication
• 7.2 Optimum order of multiplying matrices
• 7.3 Partitioning a convex polygon
• 7.4 The heuristic algorithm
• Chapter 8 NP-complete
• 8.1 Introduction
• 8.2 Polynomial algorithms
• 8.3 Nondeterministic algorithms
• 8.4 NP-complete problems
• 8.5 Facing a new problem
• Chapter 9 Local indexing algorithms
• 9.1 Mergers of algorithms
• 9.2 Maximum flows and minimum cuts
• 9.3 Maximum adjacency and minimum separation
• Chapter 10 Gomory-Hu tree
• 10.1 Tree edges and tree links
• 10.2 Contraction
• 10.3 Domination
• 10.4 Equivalent formulations
• 10.4.1 Optimum mergers of companies
• 10.4.2 Optimum circle partition
• 10.5 Extreme stars and host-feasible circles
• 10.6 The high-level approach
• 10.7 Chop-stick method
• 10.8 Relationship between phases
• 10.9 The staircase diagram
• 10.10 Complexity issues
• Appendix A Comments on Chapters 2, 5 & 6
• A.1 Ancestor trees
• A.2 Minimum surface or plateau problem
• A.3 Comments on binary trees in chapter 5
• A.3.1 A simple proof of the Hu-Tucker algorithm
• A.3.2 Binary search trees
• A.3.3 Binary search on a tape
• A.4 Comments on §6.2, bin-packing
• Appendix B Network algebra