Prentice Hall, 1993. — 863 p.Network flows is an exciting field that brings together what many students, practitioners, and researchers like best about the mathematical and computational sciences. It couples deep intellectual content with a remarkable range of applicability, covering literally thousands of applications in such wide-ranging fields as chemistry and physics, computer networking, most branches of engineering, manufacturing, public policy and social systems, scheduling and routing, telecommunications, and transportation. It is classical, dating from the work of Gustav Kirchhoff and other eminent physical scientists of the last century, and yet vibrant and current, bursting with new results and new approaches. Its heritage is rooted in the traditional fields of mechanics, engineering, and applied mathematics as well as the contemporary fields of computer science and operations research.
In writing this book we have attempted to capture these varied perspectives and in doing so to fill a need that we perceived for a comprehensive text on network flows that would bring together the old and the new, and provide an integrative view of theory, algorithms, and applications. We have attempted to design a book that could be used either as an introductory or advanced text for upper-level undergraduate or graduate students or as a reference for researchers and practitioners. We have also strived to make the coverage of this material as readable, accessible, and insightful as possible, particularly for readers with a limited background in computer science and optimization.Introduction
Paths, Trees, and Cycles
Algorithm Design and Analysis
Shortest Paths: Label-Setting Algorithms
Shortest Paths: Label-Connecting Algorithms
Maximum Flows: Basic Ideas
Maximum Flows: Polynomial Algorithms
Maximum Flows: Additional Topics
Minimum Cost Flows: Basic Algorithms
Minimum Cost Flows: Polynomial Algorithms
Minimum Cost Flows: Network Simplex Algorithms
Assignments and Matchings
Minimum Spanning Trees
Convex Cost Flows
Generalized Flows
Lagrangian Relaxation and Network Optimization
Multicommodity Flows
Computational Testing of Algorithms
Additional Applications
A: Data Structures
B: NP-Completeness
C: Linear Programming
