Combinatorial Algorithms Book

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