|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| 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
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 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
|
|
|
| Реклама |
|
|
|
|
|
О проекте