网络流:理论、算法与应用

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