|
|
 |
|
|
| Lawler E.L. — Combinatorial Optimization: Networks and Matroids |
|
|
|
| Предметный указатель |
Abadie, J. 178
Acyclic digraph 29
Acyclic networks 68, 69
adjacency 21, 22
Aigner, M. 353
Aircraft scheduling problem 139
Alternating tree 193
Amari, S. 179
Apell, P. 180
ARC 20
Arc covering problem 2
Assignment problem 2, 129, 170
Assignment problem, reduction to min-cost flow problem 186
Augmentation of capacity problem 156
Augmenting path theorem, bipartite matching 188
Augmenting path theorem, network flows 112
Augmenting path theorem, nonbipartite matching 226
Augmenting path, flow 109, 135
Augmenting sequence, matroid intersection 305, 309
Augmenting sequence, matroid parity 363, 364
Balinski, M.L. 178, 216, 262
Basic feasible solution 41, 42
Basic optimal solution 41
Basic variables 41
Basic variables, backward arc 109
Basic variables, bactracing routine, nonbipartite matching 237
Bellman — Ford algorithm 74
Bellman's equations 65
Bellman, R.E. 105
Berge, C. 58, 177, 226, 262
Bidirected flows 223—225
Bipartite graph 23
Birkhoff — von Neumann theorem 189, 222
Birkhoff, G. 297
Blattner, W. 107
Blossom, nonbipartite matching 229
Bock, F.C. 355
Borchardt. C.W. 27
Border graph 309
Boruvka, O. 298
Branch-and-bound 10—11
Bruno, J. 325, 354
Bruter, C.P. 297
Busacker, R.G. 130, 177, 178
Camerini, P. 367
Camion, P. 162, 180
Capacity constraints, elimination of 171
Capacity, arc flow 110
Capacity, cutset 112
Cardinality intersection algorithm, matroid 313
Cardinality matching algorithm, bipartite 195
Cardinality matching algorithm, nonbipartite 238
Cardinality matching problem, reduction to max-flow problem 185
Cardinality, set 17
Carre, B.A. 106
Caterer problem 133
Cheriton, D. 299
Chinese postman's algorithm 260—261
Chinese postman's problem 222, 259—261
Choquet, G. 298
Christofides, N. 58
Chromatic number problem 8
Chu, Yoeng-jiin 355
Chvatal, V. 37, 58
Circuit, matroid 269
Circulations 138—142
CLIQUE 25
Closed path 26
Cockayne, E.J. 299
Cocycle 3 1
Coefficient matrix 41
Coffman, E.G. 262
Cographic matroid 281
Combinatorial analysis 1
Common transversals 302
Complementary graph 25
Complete bipartite graph 25
Complete digraph 24
Complete graph 24
Component, graph 26
Connected graph 26
Constrained twenty questions problem 9
Contraction, graph 25
Convex bipartite graph 196
Convex combination 51
Convex polyhedron 51
Convex polytope 51
Cook, S. 12
Cost vector 41
Cost-to-time ratio cycle problem 94—97
Courant, R. 299
Crapo, H.H. 296
Crew selection problem 359
Critical path technique 165—169
Cunningham-Greene, R.A. 107
Currency conversion problem 134
Cutset 32, 111, 112
CYCLE 26
Dantzig, G.B. 43, 58, 89, 106, 107, 161, 179,180,181
Degeneracy, linear programming 47
Degree 24
Degree-constrained subgraph problem 217
Dennis, J.B. 180
Dependent set, matroid 269
Digraph 20
Dijkstra's method 70
Dijkstra, E.W. 105, 299
Dilworth theorem 141
Dilworth, R.P. 179
Dinic, E.A. 178
Dirac, G.A. 178
Directed cocycle 32
Directed cycle 28
Directed path 28
Directed spanning tree 29, 304, 348—352
Dowling, T.A. 353
Dreyfus, S.E. 98, 104, 294, 299
Duality, digraph 33—36
Duality, linear programming 53—57
Duality, matroid 280—283
Duality, matroid' intersection 3 15
Duality, nonbipartite matching 239—241
Dulmage, .A.L. 215
Dynamic programming 60
Edmonds, J. 117, 131, 157, 158, 177, 215, 217, 222, 229, 241, 243, 262, 263, 271, 276, 297, 320, 322, 336, 338, 353, 354
Elias, P. 177
Endogenous flow 136
Equivalence relation 18
Euler graph 36
Euler path 36
Even, S. 262, 354
Experimental design problem 278
Exposed node 182
Extreme point 51
Face 33
Feasible circulation problem 143
Feasible flow 109
Feasible solution, linear programming 41
Feinstein, A. 177
Fischer, M.J. 105
Flow augmenting path 109
Flow network synthesis algorithm 287
Floyd, R.W. 106
Ford, L.R. 105, 177, 181, 215
Forest 27
Forward arc 109
Frank, H. 177
Fredman, M.L. 106
Frisch, I. 177
Fujii, M. 219, 261
|
Fujisawa, T. 179
Fulkerson, D.R. 104, 109, 177, 179, 180, 181, 215, 271, 297, 322, 353
Gabow, H. 263
Gale optimality 277
Gale — Shapley matching problem 211
Gale, D. 207, 211, 212, 216, 277, 297
Garey, M.R. 299
Geometric dual 33
Geometric interpretation, linear programming 48—57
Ghouila-Houri, A. 177
Gilbert, E.N. 299
Gilmore, P.C. 209, 216
Gilmore-Gomory matching 207—210
Glicksberg, I. 215
Glover, F. 196, 215
Gomory, R.E. 174, 181, 209, 216, 299
Gowen, P.J. 130, 178
Graham, R.L. 262, 299
Graph 20
Graphic matroid 268
Graphoid 283
Greedy algorithm 267, 275—277
Greedy algorithm, matric matroid 279
Greedy algorithm, variations 283—285
Grinold, R.C. 179
Gross, O. 198, 215
Guy, R. 12
Hadley, G 58
Hall, M., Jr. 215
Hall, P. 353
Hamilton cycle 37
Hamilton graph 37
Hanan, M. 299
Harary, R. 58, 297
Heuristic methods 10—12
Hitchcock — Koopmans transportation problem 169, 171
Hitchcock, F.L. 181
Hoffman, A.J. 140, 161, 779, 180, 214
Holzmann, C.A. 297
Homosexual marriage problem 220
Hopcroft, J.E. 2§ 2&
Hu, T.C. 12, 104, 174—176, 177, 178, 181, 287, 299
Huffman, D.A. 2
Hungarian method, weighted bipartite matching 201, 207
Hungarian tree, bipartite matching 193
Hungarian tree, nonbipartite matching 240
Hypergraph 361
Hyperplane 51
In-degree 24
incidence 21
Independent set, matroid 268
Integer linear programming 10, 11
Integral circulation theorem 160
Integral flow theorem 113
Integrality theorem, bipartite matching 189
Integrality, flow 160—165
Intersection graph 37
Iri, M. 177, 178, 179, 354
Jarvis, J.J. 178
Jewell, W.S. 130, 178
Jezior, A.M. 178
Johnson, D.B. 104
Johnson, D.S. 299
Johnson, E.L. 263
Kajitani, V. 325, 353
Kantorovitch, L. 181
Kariv, O. 262
Karp, R.M. 9, 12, 23, 117, 131, 157, 158, 177, 215, 262, 355
Kasami, T. 261
Kautz, W.H. 298
Kelley, J.E., Jr. 180
Kilter conditions 144
Kilter diagram 144
Kilter number 144
Kishi, G. 325, 353
Klee, V. 60, 73, 191, 298
Klein, M. 130, 178, 200, 216
Knapsack problem 62
Knuth, D.E. 12
Koenig — Egervary theorem 190—231
Krogdahl, S. 310, 311, 327—331, 352
Kruskal, J.B. 161, 180, 266, 298
Kuhn, H.W. 181, 216
Kundu, S. 317, 353
Kurotowski graphs 33
Kwan, Mei-ko 222, 259, 263
Labeling procedure, nonbipartite matching 235
Lageweg, B.J. 354
Land, A.H. 104
Lawler, E.L. 107, 108, 3 17, 352, 353, 367
Lehman, A. 354
Lexicography 18, 19
Line graph 38
Linear independence 41
Linear programming 39—57
Liu, C.L. 12
Liu, Tseng-hong 355
Lockhart, S. 263
Longest path problem 9, 62
Loop 20
Losses and gains, network with 134—138
Lower bounds, flow 138
Machine sequencing problem 9
Maffioli, F. 367
Markowitz, H. 178, 214
Marriage problem 189
Marshall. J. 108
Matching matroid 271
Matching, defined 182
Matrix multiplication 83
Matroid defined 268
Matroid matching problem 359
Matroid of graph 268
Matroid parity problem, generalized 364—367
Matroid partitioning algorithm 320
Matroid partitioning problem 319—323, 356
Matroid polyhedra 334—338
Matroid polyhedral intersection theorem 338
Matroid sum 318
Maurras, J.F. 178
Max cut problem 8
Max flow problem 143
Max-flow min-cut theorem 113
Max-flow min-cut theorem, generalized 121, 140
Max-flow min-cut theorem, linear programming interpretation 123—125
Max-min matching, bipartite 183, 197—199
Max-min matching, nonbipartite 241
Maximal flow algorithm 115
Maximal flow algorithm, efficiency 116—119
Maximal spanning tree algorithm 286
Maximal spanning tree problem 266, 278
Mayeda 179
McNaughton, R. 106
Melzak, Z.A. 299
Mendelsohn — Dulmage theorem 191
Mendelsohn — Dulmage theorem, matroid generalization 3 17
Mendelsohn, N.S. 215
Menger, K. 121, 122
Meyer, A.R. 705
Min cost flow algorithm 131
Min cost flow problem 143
Min cost flow problem, reduction to weighted matching problem 187
Min cut problem 2
Min flow-max cut theorem 141
Minty, G. 32, 109, 179, 180, 282, 283
Monge 180
Moore, E.F. 105
Moore, J.M. 2
Multicommodity flows 173—176
Multicommodity flows, analysis problem 175
|
|
|
| Реклама |
|
|
|
|
|
|
О проекте