Combinatorial Algorithms

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