Network Flows. Theory, Algorithms, and Applications

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.<br/>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<br/>Paths, Trees, and Cycles<br/>Algorithm Design and Analysis<br/>Shortest Paths: Label-Setting Algorithms<br/>Shortest Paths: Label-Connecting Algorithms<br/>Maximum Flows: Basic Ideas<br/>Maximum Flows: Polynomial Algorithms<br/>Maximum Flows: Additional Topics<br/>Minimum Cost Flows: Basic Algorithms<br/>Minimum Cost Flows: Polynomial Algorithms<br/>Minimum Cost Flows: Network Simplex Algorithms<br/>Assignments and Matchings<br/>Minimum Spanning Trees<br/>Convex Cost Flows<br/>Generalized Flows<br/>Lagrangian Relaxation and Network Optimization<br/>Multicommodity Flows<br/>Computational Testing of Algorithms<br/>Additional Applications<br/>A: Data Structures<br/>B: NP-Completeness<br/>C: Linear Programming