| Preface | p. iii |
| Introduction | p. 1 |
| What is Combinatorial Optimization? | p. 1 |
| Some Representative Optimization Problems | p. 2 |
| When is a Problem Solved? | p. 4 |
| The Criterion of Polynomial Boundedness | p. 5 |
| Some Apparently Nonpolynomial-Bounded Problems | p. 8 |
| Methods of Solution | p. 10 |
| Comments and References | p. 12 |
| Mathematical Preliminaries | p. 15 |
| Mathematical Prerequisites | p. 15 |
| Sets and Relations | p. 16 |
| Graphs and Digraphs | p. 20 |
| Subgraphs, Cliques, Multigraphs | p. 24 |
| Connectivity in Graphs | p. 26 |
| Connectivity in Digraphs | p. 28 |
| Cocycles and Directed Cocycles | p. 31 |
| Planarity and Duality | p. 32 |
| Eulerian and Hamiltonian Graphs | p. 36 |
| Linear Programming Problems | p. 39 |
| The Simplex Method | p. 43 |
| Geometric Interpretation | p. 48 |
| Duality Theory | p. 53 |
| Comments and References | p. 58 |
| Shortest Paths | p. 59 |
| Introduction | p. 59 |
| Some Problem Formulations | p. 61 |
| Bellman's Equations | p. 65 |
| Acyclic Networks | p. 68 |
| Networks with Positive Arcs: Dijkstra's Method | p. 70 |
| Solution by Successive Approximations: Bellman-Ford Method Method | p. 74 |
| Improvements in Efficiency: Yen's Modifications | p. 76 |
| Linear Programming Interpretation and Relaxation Procedures | p. 77 |
| Shortest Paths between all Pairs of Nodes: Matrix Multiplication | p. 82 |
| Floyd-Warshall Method | p. 86 |
| Detection of Negative Cycles | p. 90 |
| Networks with Transit Times | p. 92 |
| The Minimal Cost-to-time Ratio Cycle Problem | p. 94 |
| M Shortest Paths: Dreyfus Method | p. 98 |
| M Shortest Paths without Repeated Nodes | p. 100 |
| Comments and References | p. 104 |
| Network Flows | p. 109 |
| Introduction | p. 109 |
| Maximal Flows | p. 110 |
| Maximal Flow Algorithm | p. 114 |
| Efficiency of the Maximal Flow Algorithm | p. 116 |
| Combinatorial Implications of Max-Flow Min-Cut Theorem | p. 120 |
| Linear Programming Interpretation of Max-Flow Min-Cut Theorem | p. 123 |
| Minimum Cost Flows | p. 129 |
| Networks with Losses and Gains | p. 134 |
| Lower Bounds and Circulations | p. 138 |
| The Out-of-Kilter Method | p. 142 |
| Theoretical Improvement in Efficiency of Out-of-Kilter Method | p. 157 |
| Integrality of Flows and the Unimodular Property | p. 160 |
| Application to Project Scheduling | p. 165 |
| Transhipment and Transportation Problems | p. 169 |
| Multiterminal and Multicommodity Flows | p. 173 |
| Comments and References | p. 177 |
| Bipartite Matching | p. 182 |
| Introduction | p. 182 |
| Problem Reductions and Equivalences | p. 184 |
| Counterparts of Network Flow Theorems | p. 188 |
| Mendelsohn-Dulmage Theorem | p. 191 |
| Cardinality Matching Algorithm | p. 193 |
| A Special Case: Convex Graphs | p. 196 |
| Max-Min Matching | p. 197 |
| The Hungarian Method for Weighted Matching | p. 201 |
| A Special Case: Gilmore-Gomory Matching | p. 207 |
| A Novel Optimization Criterion: Gale-Shapley Matching | p. 211 |
| Comments and References | p. 214 |
| Nonbipartite Matching | p. 217 |
| Introduction | p. 217 |
| Problem Formulations | p. 218 |
| Bidirected Flows | p. 223 |
| Augmenting Paths | p. 226 |
| Trees and Blossoms | p. 229 |
| Cardinality Matching Algorithm | p. 233 |
| Duality Theory | p. 239 |
| Linear Programming Formulation of Weighted Matching Problem | p. 242 |
| An O (n[superscript 4]) Weighted Matching Algorithm | p. 247 |
| An O (n[superscript 3]) Weighted Matching Algorithm | p. 252 |
| The Chinese Postman's Problem | p. 259 |
| Comments and References | p. 261 |
| Matroids and the Greedy Algorithm | p. 264 |
| Introduction | p. 264 |
| Three Apparently Unrelated Optimization Problems | p. 265 |
| Matroid Definitions | p. 268 |
| Matching, Transversal, and Partition Matroids | p. 271 |
| Matroid Axiomatics | p. 273 |
| The Matroid Greedy Algorithm | p. 275 |
| Applications of the Greedy Algorithm | p. 278 |
| Matroid Duality | p. 280 |
| Variations of the Greedy Algorithm | p. 283 |
| Prim Spanning Tree Algorithm | p. 285 |
| An Application: Flow Network Synthesis | p. 286 |
| The Steiner Problem and Other Dilemmas | p. 290 |
| Comments and References | p. 296 |
| Matroid Intersections | p. 300 |
| Introduction | p. 300 |
| Problem Formulations | p. 301 |
| Augmenting Sequences and Border Graphs | p. 306 |
| Cardinality Intersection Algorithm | p. 313 |
| Duality Theory | p. 315 |
| Generalized Mendelsohn-Dulmage Theorem, Matroid Sums and Matroid Partitions | p. 317 |
| Matroid Partitioning Algorithm | p. 320 |
| The Shannon Switching Game | p. 324 |
| Weighted Augmenting Sequences | p. 326 |
| Primal Weighted Intersection Algorithm | p. 332 |
| Matroid Polyhedra | p. 334 |
| Explanation of Primal-Dual Method | p. 339 |
| Primal-Dual Weighted Intersection Algorithm | p. 345 |
| A Special Case: Directed Spanning Trees | p. 348 |
| Comments and References | p. 352 |
| The Matroid Parity Problem | p. 356 |
| Introduction | p. 356 |
| Problem Formulations | p. 358 |
| Augmenting Sequences | p. 363 |
| Generalizations | p. 364 |
| Comments and References | p. 367 |
| Author Index | p. 368 |
| Subject Index | p. 371 |
| Table of Contents provided by Syndetics. All Rights Reserved. |
