目錄
PREFACE
1 INTRODUCTION
1.1 Introduction
1.2 Network Flow Problems
1.3 Applications
1.4 Summary
Reference Notes
Exercises
2 PATHS, TREES, AND CYCLES
2.1 Introduction
2.2 Notation and Definitions
2.3 Network Representations
2.4 Network Transformations
2.5 Summary
Reference Notes
Exercises
3 ALGORITHM DESIGN AND ANALYSIS
3.1 Introduction
3.2 Complexity Analysis
3.3 Developing Polynomial-Time Algorithms
3.4 Search Algorithms
3.5 Flow Decomposition Algorithms
3.6 Summary
Reference Notes
Exercises
4 SHORTEST PATHS: LABEL-SETTING ALGORITHMS
4.1 Introduction
4.2 Applications
4.3 Tree of Shortest Paths
4.4 Shortest Path Problems in Acyclic Networks
4.5 Dijkstra's Algorithm
4.6 Dial's Implementation
4.7 Heap Implementations
4.8 Radix Heap Implementation
4.9 Summary
Reference Notes
Exercises
5 SHORTEST PATHS: LABEL-CORRECTING ALGORITHMS
5.1 Introduction
5.2 Optimality Conditions
5.3 Generic Label-Correcting Algorithms
5.4 Special Implementations of the Modified Label-Correcting Algorithm,
5.5 Detecting Negative Cycles
5.6 All-Pairs Shortest Path Problem
5.7 Minimum Cost-to-Time Ratio Cycle Problem
5.8 Summary
Reference Notes
Exercises
6 MAXIMUM FLOWS: BASIC DEAS
6.1 Introduction
6.2 Applications
6.3 Flows and Cuts
6.4 Generic Augmenting Path Algorithm
6.5 Labeling Algorithm and the Max-Flow Min-Cut Theorem
6.6 Combinatorial Implications of the Max-Flow Min-Cut Theorem
6.7 Flows with Lower Bounds
6.8 Summary
Reference Notes
Exercises
7 MAXIMUM FLOWS: POLYNOMIAL ALGORITHMS
7.1 Introduction
7.2 Distance Labels
7.3 Capacity Scaling Algorithm
7.4 Shortest Augmenting Path Algorithm
7.5 Distance Labels and Layered Networks
7.6 Generic Preflow-Push Algorithm
7.7 FIFO Preflow-Push Algorithm
7.8 Highest-Label Preflow-Push Algorithm
7.9 Excess Scaling Algorithm
7.10 Summary
Reference Notes
Exercises
8 MAXIMUM FLOWS: ADDITIONAL TOPICS
8.1 Introduction
8.2 Flows in Unit Capacity Networks
8.3 Flows in Bipartite Networks
8.4 Flows in Planar Undirected Networks
8.5 Dynamic Tree
8.6 Implementations
8.7 Network Connectivity
8.8 All-Pairs Minimum Value Cut Problem
8.9 Summary
Reference Notes
Exercises
9 MINIMUM COST FLOWS: BABIC ALGORITHMS
9.1 Introduction
9.2 Applications
9.3 Optimality Conditions
9.4 Minimum Cost Flow Duality
9.5 Relating Optimal Flows to Optimal Node Potentials
9.6 Cycle-Canceling Algorithm and the Integrality Property
9.7 Successive Shortest Path Algorithm
9.8 Primal-Dual Algorithm
9.9 Out-of-Kilter Algorithm
9.10 Relaxation Algorithm
9.11 Sensitivity Analysis
9.12 Summary
Reference Notes
Exercises
10 MINIMUM COST FLOWB: POLYNOMIAL ALGORITHMS
10.1 Introduction
10.2 Capacity Scaling Algorithm
10.3 Cost Scaling Algorithm
10.4 Double Scaling Algorithm
10.5 Minimum Mean Cycle-Canceling Algorithm
10.6 Repeated Capacity Scaling Algorithm
10.7 Enhanced Capacity Scaling Algorithm
10.8 Summary
Reference Notes
Exercises
11 MINIMUM COST FLOWS: NETWORK SIMPLEX ALGORITHMS
11.1 Introduction
11.2 Cycle Free and Spanning Tree Solutions
11.3 Maintaining a Spanning Tree Structure
11.4 Computing Node Potentials and Flows
11.5 Network Simplex Algorithm
11.6 Strongly Feasible Spanning Trees
11.7 Network Simplex Algorithm for the Shortest Path Problem
11.8 Network Simplex Algorithm for the Maximum Flow Problem
11.9 Related Network Simplex Algorithms
11.10 Sensitivity Analysis
11.11 Relationship to Simplex Method
11.12 Unimodularity Property
11.13 Summary
Reference Notes
Exercises
12 ASSIGNMENTS AND MATCHINGS
12.1 Introduction
12.2 Applications
12.3 Bipartite Cardinality Matching Problem
12.4 Bipartite Weighted Matching Problem
12.5 Stable Marriage Problem
12.6 Nonbipartite Cardinality Matching Problem
12.7 Matchings and Paths
12.8 Summary
Reference Notes
Exercises
13 MINIMUM SPANNING TREES
13.1 Introduction
13.2 Applicattons
13.3 Optimality Conditions
13.4 Kruskal's Algorithm
13.5 Prim's Algorithm
13.6 Sollin's Algorithm
13.7 Minimum Spanning Trees and Matroids
13.8 Minimum Spanning Trees and Linear Programming
13.9 Summary
Reference Notes
Exercises
14 CONVEX COST FLOWS
14.1 Introduction
14.2 Applications
14.3 Transformation to a Minimum Cost Flow Problem
14.4 Pseudopolynomial-Time Algorithms
14.5 Polynomial-Time Algorithm
14.6 Summary
Reference Notes
Exercises
15 GENERALIZED FLOWS
15.1 Introduction
15.2 Applications
15.3 Augmented Forest Structures
15.4 Determining Potentials and Flows for an Augmented Forest Structure
15.5 Good Augmented Forests and Linear Programming
15.6 Bases Generalized Network Simplex Algorithm
15.7 Summary
Reference Notes
Exercises
16 LAGRANGIAN RELAXATION AND NETWORK OPTIMTZATION
16.1 Introduction
16.2 Problem Relaxations and Branch and Bound
16.3 Lagrangian Relaxation Technique
16.4 Lagrangian Relaxation and Linear Programming
16.5 Applications of Lagrangian Relaxation
16.6 Summary
Reference Notes
Exercises
17 MULTICOMMODITY FLOWS
17.1 Introduction
17.2 Applications
17.3 Optimality Conditions
17.4 Lagrangian Relaxation
17.5 Column Generation Approach
17.6 Dantzig-Wolfe Decomposition
17.7 Resource-Directive Decomposition
17.8 Basis Partitioning
17.9 Summary
Reference Notes
Exercises
18 COMPUTATIONAL TESTING OF ALGORITHMS
18.1 Introduction
18.2 Representative Operation Counts
18.3 Application to Network Simplex Algorithm
18.4 Summary
Reference Notes
Exercises
19 ADDITIONAL APPLICATIONS
19.1 Introduction
19.2 Maximum Weight Closure of a Graph
19.3 Data Scaling
19.4 Science Applications
19.5 Project Management
19.6 Dynamic Flows
19.7 Arc Routing Problems
19.8 Facility Layout and Location
19.9 Production and Inventory Planning
19.10 Summary
Reference Notes
Exercises
APPENDIX A DATA STRUCTURES
A.1 Introduction
A.2 Elementary Data Structures
A.3 d-Heaps
A.4 Fibonacci Heaps
Reference Notes
APPENDIX B N-COMPLETENESS
B.1 Introduction
B.2 Problem Reductions and Transformations
B.3 Problem Classes P, N, NoP-Complete, and N-Hard
B.4 Proving NP-Completeness Results
B.5 Concluding Remarks
Reference Notes
APPENDIX C LINEAR PROGRAMMING
C.1 Introduction
C.2 Graphical Solution Procedure
C.3 Basic Feasible Solutions
C.4 Simplex Method
C.5 Bounded Variable Simplex Method
C.6 Linear Programming Duality
Reference Notes
REFERENCES
INDEX
[