Title:
Network flows : theory, algorithms, and applications
Personal Author:
Publication Information:
Englewood Cliffs, NJ : Prentice Hall, 1993
ISBN:
9780136175490
Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000002955239 | T57.85 A48 1993 | Open Access Book | Book | Searching... |
Searching... | 30000004992909 | T57.85 A48 1993 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
A comprehensive introduction to network flows that brings together the classic and the contemporary aspects of the field, and provides an integrative view of theory, algorithms, and applications.
presents in-depth, self-contained treatments of shortest path, maximum flow, and minimum cost flow problems, including descriptions of polynomial-time algorithms for these core models. emphasizes powerful algorithmic strategies and analysis tools such as data scaling, geometric improvement arguments, and potential function arguments. provides an easy-to-understand descriptions of several important data structures, including d-heaps, Fibonacci heaps, and dynamic trees. devotes a special chapter to conducting empirical testing of algorithms. features over 150 applications of network flows to a variety of engineering, management, and scientific domains. contains extensive reference notes and illustrations.
Table of Contents
1 Introduction |
2 Paths, Trees and Cycles |
3 Algorithm Design and Analysis |
4 Shortest Paths: Label Setting Algorithms |
5 Shortest Paths: Label Correcting Algorithms |
6 Maximum Flows: Basic Ideas |
7 Maximum Flows: Polynomial Algorithms |
8 Maximum Flows: Additional Topics |
9 Minimum Cost Flows: Basic Algorithms |
10 Minimum Cost Flows: Polynomial Algorithms |
11 Minimum Cost Flows: Network Simplex Algorithms |
12 Assignments and Matchings |
13 Minimum Spanning Trees |
14 Convex Cost Flows |
15 Generalized Flows |
16 Lagrangian Relaxation and Network Optimization |
17 Multicommodity Flows |
18 Computational Testing of Algorithms |
19 Additional Applications |
Appendix A Data Structures |
Appendix B NP-Completeness |
Appendix C Linear Programming |
Index |