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 for Combinatorial Algorithms: Enlarged Second Edition

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 comp
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

Join the Dover Family | Track Your Order | Your Account | Shipping Rates and Policies | Returns | Customer Service | Free Samples | About Dover | Privacy Notice | Terms of Use | Join Our Staff | Free Catalogs