Network Flows: Theory, Algorithms, and Applications

Cover......Page 1
NETWORK FLOWS: Theory, Algorithms, and Applications......Page 2
Copyright......Page 3
CONTENTS......Page 6
PREFACE......Page 12
1.1 Introduction,......Page 18
1.2 Network Flow Problems,......Page 21
1.3 Applications,......Page 26
1.4 Summary,......Page 35
Reference Notes,......Page 36
Exercises,......Page 37
2.1 Introduction,......Page 40
2.2 Notation and Definitions,......Page 41
2.3 Network Representations,......Page 48
2.4 Network Transformations,......Page 55
2.5 Summary,......Page 63
Exercises,......Page 64
3.1 Introduction,......Page 70
3.2 Complexity Analysis,......Page 73
3.3 Developing Polynomial-Time Algorithms,......Page 83
3.4 Search Algorithms,......Page 90
3.5 Flow Decomposition Algorithms,......Page 96
3.6 Summary,......Page 101
Reference Notes,......Page 102
Exercises,......Page 103
4.1 Introduction,......Page 110
4.2 Applications,......Page 114
4.3 Tree of Shortest Paths,......Page 123
4.4 Shortest Path Problems in Acyclic Networks,......Page 124
4.5 Dijkstra's Algorithm,......Page 125
4.6 Dial's Implementation,......Page 130
4.7 Heap Implementations,......Page 132
4.8 Radix Heap Implementation,......Page 133
4.9 Summary,......Page 138
Reference Notes,......Page 139
Exercises,......Page 141
5.1 Introduction,......Page 150
5.2 Optimality Conditions,......Page 152
5.3 Generic Label-Correcting Algorithms,......Page 153
5.4 Special Implementations of the Modified Label-Correcting Algorithm,......Page 158
5.5 Detecting Negative Cycles,......Page 160
5.6 All-Pairs Shortest Path Problem,......Page 161
5.7 Minimum Cost-to-Time Ratio Cycle Problem,......Page 167
5.8 Summary,......Page 171
Reference Notes,......Page 173
Exercises,......Page 174
6.1 Introduction,......Page 183
6.2 Applications,......Page 186
6.3 Flows and Cuts,......Page 194
6.4 Generic Augmenting Path Algorithm,......Page 197
6.5 Labeling Algorithm and the Max-Flow Min-Cut Theorem,......Page 201
6.6 Combinatorial Implications of the Max-Flow Min-Cut Theorem,......Page 205
6.7 Flows with Lower Bounds,......Page 208
6.8 Summary,......Page 213
Reference Notes,......Page 214
Exercises,......Page 215
7.1 Introduction,......Page 224
7.2 Distance Labels,......Page 226
7.3 Capacity Scaling Algorithm,......Page 227
7.4 Shortest Augmenting Path Algorithm,......Page 230
7.5 Distance Labels and Layered Networks,......Page 238
7.6 Generic Preflow-Push Algorithm,......Page 240
7.7 FIFO Preflow-Push Algorithm,......Page 248
7.8 Highest-Label Preflow-Push Algorithm,......Page 250
7.9 Excess Scaling Algorithm,......Page 254
Reference Notes,......Page 258
Exercises,......Page 260
8.1 Introduction,......Page 267
8.2 Flows in Unit Capacity Networks,......Page 269
8.3 Flows in Bipartite Networks,......Page 272
8.4 Flows in Planar Undirected Networks,......Page 277
8.5 Dynamic Tree Implementations,......Page 282
8.6 Network Connectivity,......Page 290
8.7 All-Pairs Minimum Value Cut Problem,......Page 294
8.8 Summary,......Page 302
Reference Notes,......Page 304
Exercises,......Page 305
9.1 Introduction,......Page 311
9.2 Applications,......Page 315
9.3 Optimality Conditions,......Page 323
9.4 Minimum Cost Flow Duality,......Page 327
9.5 Relating Optimal Flows to Optimal Node Potentials,......Page 332
9.6 Cycle-Canceling Algorithm and the Integrality Property,......Page 334
9.7 Successive Shortest Path Algorithm,......Page 337
9.8 Primal-Dual Algorithm,......Page 341
9.9 Out-of-Kilter Algorithm,......Page 343
9.10 Relaxation Algorithm,......Page 349
9.11 Sensitivity Analysis,......Page 354
9.12 Summary,......Page 356
Reference Notes,......Page 358
Exercises,......Page 361
10.1 Introduction,......Page 374
10.2 Capacity Scaling Algorithm,......Page 377
10.3 Cost Scaling Algorithm,......Page 379
10.4 Double Scaling Algorithm,......Page 390
10.5 Minimum Mean Cycle-Canceling Algorithm,......Page 393
10.6 Repeated Capacity Scaling Algorithm,......Page 399
10.7 Enhanced Capacity Scaling Algorithm,......Page 404
10.8 Summary,......Page 412
Reference Notes,......Page 413
Exercises,......Page 414
11.1 Introduction,......Page 419
11.2 Cycle Free and Spanning Tree Solutions,......Page 422
11.3 Maintaining a Spanning Tree Structure,......Page 426
11.4 Computing Node Potentials and Flows,......Page 428
11.5 Network Simplex Algorithm,......Page 432
11.6 Strongly Feasible Spanning Trees,......Page 438
11.7 Network Simplex Algorithm for the Shortest Path Problem,......Page 442
11.8 Network Simplex Algorithm for the Maximum Flow Problem,......Page 447
11.9 Related Network Simplex Algorithms,......Page 450
11.10 Sensitivity Analysis,......Page 456
11.11 Relationship to Simplex Method,......Page 458
11.12 Unimodularity Property,......Page 464
11.13 Summary,......Page 467
Reference Notes,......Page 468
Exercises,......Page 470
12.1 Introduction,......Page 478
12.2 Applications,......Page 480
12.3 Bipartite Cardinality Matching Problem,......Page 486
12.4 Bipartite Weighted Matching Problem,......Page 487
12.S Stable Marriage Problem,......Page 490
12.6 Nonbipartite Cardinality Matching Problem,......Page 492
12.7 Matchings and Paths,......Page 511
12.8 Summary,......Page 515
Reference Notes,......Page 516
Exercises,......Page 518
13.1 Introduction,......Page 527
13.2 Applications,......Page 529
13.3 Optimality Conditions,......Page 533
13.4 Kruskal's Algorithm,......Page 537
13.S Prim's Algorithm,......Page 540
13.6 Sollin's Algorithm,......Page 543
13.7 Minimum Spanning Trees and Matroids,......Page 545
13.8 Minimum Spanning Trees and Linear Programming,......Page 547
13.9 Summary,......Page 550
Reference Notes,......Page 552
Exercises,......Page 553
14.1 Introduction,......Page 560
14.2 Applications,......Page 563
14.3 Transformation to a Minimum Cost Flow Problem,......Page 568
14.4 Pseudopolynomial-Time Algorithms,......Page 571
14.5 Polynomial-Time Algorithm,......Page 573
14.6 Summary,......Page 577
Reference Notes,......Page 578
Exercises,......Page 579
15.1 Introduction,......Page 583
15.2 Applications,......Page 585
15.3 Augmented Forest Structures,......Page 589
15.4 Determining Potentials and Flows for an Augmented Forest Structure,......Page 594
15.5 Good Augmented Forests and Linear Programming Bases,......Page 599
15.6 Generalized Network Simplex Algorithm,......Page 600
Reference Notes,......Page 608
Exercises,......Page 610
16.1 Introduction,......Page 615
16.2 Problem Relaxations and Branch and Bound,......Page 619
16.3 Lagrangian Relaxation Technique,......Page 622
16.4 Lagrangian Relaxation and Linear Programming,......Page 632
16.5 Applications of Lagrangian Relaxation,......Page 637
16.6 Summary,......Page 652
Reference Notes,......Page 654
Exercises,......Page 655
17.1 Introduction,......Page 666
17.2 Applications,......Page 670
17.3 Optimality Conditions,......Page 674
17.4 Lagrangian Relaxation,......Page 677
17.5 Column Generation Approach,......Page 682
17.6 Dantzig-Wolfe Decomposition,......Page 688
17.7 Resource-Directive Decomposition,......Page 691
17.8 Basis Partitioning,......Page 695
17.9 Summary,......Page 699
Reference Notes,......Page 701
Exercises,......Page 703
18.1 Introduction,......Page 712
18.2 Representative Operation Counts,......Page 715
18.3 Application to Network Simplex Algorithm,......Page 719
Reference Notes,......Page 730
Exercises,......Page 732
19.1 Introduction,......Page 734
19.2 Maximum Weight Closure of a Graph,......Page 736
19.3 Data Scaling,......Page 742
19.4 Science Applications,......Page 745
19.5 Project Management,......Page 749
19.6 Dynamic Flows,......Page 754
19.7 Arc Routing Problems,......Page 757
19.8 Facility Layout and Location,......Page 761
19.9 Production and Inventory Planning,......Page 765
19.10 Summary,......Page 772
Reference Notes,......Page 776
Exercises,......Page 777
A.1 Introduction,......Page 782
A.2 Elementary Data Structures,......Page 783
A.3 d-Heaps,......Page 790
A.4 Fibonacci Heaps,......Page 796
Reference Notes,......Page 804
B.1 Introduction,......Page 805
B.2 Problem Reductions and Transformations,......Page 807
B.3 Problem Classes P, NP, NP-Complete, and NP-Hard,......Page 809
B.4 Proving NP-Completeness Results,......Page 813
B.5 Concluding Remarks,......Page 817
Reference Notes,......Page 818
C.1 Introduction,......Page 819
C.2 Graphical Solution Procedure,......Page 821
C.3 Basic Feasible Solutions,......Page 822
C.4 Simplex Method,......Page 827
C.5 Bounded Variable Simplex Method,......Page 831
C.6 Linear Programming Duality,......Page 833
Reference Notes,......Page 837
REFERENCES,......Page 838
INDEX,......Page 857