|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Papadimitriou C.H., Steiglitz K. — Combinatorial Optimization: Algorithms and Complexity |
|
|
|
| Предметный указатель |
Flowshop scheduling 444—48 470
Floyd, R.W. 136 306
Floyd-Warshall algorithm 129—33
for statement 24
Ford, L.R.Jr. 115 116 126 135 141 153 245 453
Forest 22
Forest, maximum-weight 278
FOUR PARTITION 402
FPTAS, see “Fully polynomial-time approximation scheme”
Fractional-dual algorithm 330
Fractional-dual algorithm, its finiteness 237—39
Frank, H. 484
Free edge 219
Freudenstein, F. 485
Fridshal, D. 484
Fridshal, R. 484
Fujii, M. 246
Fulkerson, D.R. 115 116 126 135 141 153 245 306 324
Fully polynomial-time approximation scheme (or FPTAS) 426 430
Gale, D. 65 86 87
Galil, Z. 216 217
Gantmacher, F.R. 192
Gap 482
Garey, M.R. 155 381 401 404 431 432 445 453 486
Garfinkel, R.S. 341
Gass, S.I. 65
Gaussian elimination 173
Gavril, F. 405 432
Gavurin, M.K. 154
Generating row 329
Ghouilla-Houri, A. 305
Gilmore, P.C. 270 405
Global optimum 8—10
Glover, F. 154
Gol'Shtein, E.G. 65 87
Goldfarb, D. 51 66 191
Goldstein, A.J. 485
Gomory cut 328
GomoryT-R.E. 270 328 330 331 340 341 405
Gonzalez, T. 432
GOTO statement 25
Gowen, P.J. 152
Graham, R.L. ~431
Graph 20 160—61
Graph coloring 377 378 403
Graph, admissible 258
Graph, biconnected 214
Graph, bidirected 244
Graph, bipartite 21
Graph, chordal 403
Graph, connected 22 196
Graph, current 260
Graph, directed see “Digraph”
Graph, k-regular 482
Graph, multi- 20
Graph, planar 302
Graph, undirected 20
Graph, weighted 22
Graphic matroid 287
Gratzer, F.J. 484
Greedy algorithm 278—80 282 285
Groetschel, M. 192
Gruenbaum, B. 66
Hadley, G. 18 65
Halfspace 34
Hall, M.Jr. 245
Halting problem 156 185 347
HAMILTON CIRCUIT 347 366 383 392 395 427 479
HAMILTON CIRCUIT, DIRECTED 391 404
HAMILTON CIRCUIT, RESTRICTED 477
HAMILTON COMPLETION 404
Hamilton path 294 300
Hamilton walk 431
Head of an arc 244
Head-partition matroid 288
Held, M. 441 453 456 484
Heller, I. 325
Heuristic 401
Hitchcock problem 143
Hitchcock, F.L. 143 154
Hitting Set 404
Hoffman, A.J. 324
Hopcroft, J.E. 24 136 190 216 246 382
Hu, T.C. 65 341 405
Hungarian method 144 248—55 267
Hyperplane 35
Hyperplane, supporting 36
I (unit matrix) 19
Ibarra, O.H. 432
If statement 24
Ignall, E. 446 452
ILP see “Integer linear programming”
Incidence matrix 318
Incidence matrix, arc-chain 92
Incidence matrix, node-arc 75
Incident edge 21
Incremental network 139
Indegree 21
Independent set 361 363 403 430
Independent subset 280
Inner node 219 260
Instance of an optimization problem 4 344
INTEGER KNAPSACK 374 376 387 419
Integer linear programming (or ILP) 3 307—09 344 350 359 433—38
Integer linear programming (or ILP), mixed 310 313 324 438
Integer part 328
Interior of a polytope 175—76
Inverse matrix method see “Revised simplex algorithm”
Iri, M. 152
Itai, A. 217
Jarvis, J.J. 65
Jeroslow, R.J. 190
Jewell, W.S. 152
Job scheduling with deadlines (or JSD) 475
Johnson, D.B. 404
Johnson, D.S. 155 381 401 404 431 432 445 453 486
Johnson, E.L. 270
Johnson, S.M. 324
JSD see “Job scheduling with deadlines”
Judin, D.B. 65 87 191
k-change neighborhood 7—8 455
k-regular graph 482
Kantorovitch, L. 154
Karel, C 452
Kariv, O. 246
Karney, D. 154
Karp, R.M. 126 135 153 192 216 246 306 381 441 453 456 484 485
Karzanov, A.V. 216
Kasami, T. 246
Kashdan, S.D. 404
Kernighan, B.W. 465 468 469 470 484
Khachian, L.G. 191
kill 436
Kim, C.E. 432
Klee, V. 190
Klein, M. 140 152
Kleitman, D.J. 484
Klingman, D. 154
Knapsack problem 375 see INTEGE
Knuth, D.E. 382
Koenig-Egervary Theorem 134
Koopmans, T.C. 154
Kotiah, T.C.T. 66
Kraitchik, M. 18
Krone, M.J. 470 485
Kruskal, J.B. 305 324
Kuhn, H.W. 51 66 87 116 144 154 269
Kuhn-Tucker conditions 2
Kumar, M.P. 217
Kwan, M. 270
| Label 121—22 198
Labeling algorithm 120—28 162—63 200—202
Labeling algorithm, its finitcness 124—28
Langlcy, R.W. 136
Langrana, N. 486
Lasdon, L.S. 103
Law A.M. 453
Lawier, E.L. 153 270 306 405 432 452
Layered network 205 448
Lee, T.W. 486
Length of a path or circuit 21
Lenstra, H.W. 341
Lenstra, J.K. 381
Lesk, A.B. 485
Lewis, H.R. 192
Lewis, P.M. 432
Lexicographically (or lex-), equal 334
Lexicographically (or lex-), greater-than 334
Lexicographically (or lex-), less-than 334
Lexicographically (or lex-), negative 334
Lexicographically (or lex-), positive 334
Lexicographically (or lex-), zero 334
Li see “Linear inequalities”
Lin, S. 18 456 484
Linear inequalities (or LI) 170 172 174 385—86
Linear program (or LP) 5—6
Linear program (or LP), in canonical form 27
Linear program (or LP), in general form 28
Linear program (or LP), in standard form 28
Linear programming problem (or LP) 1 5—6
Linear strict inequalities (or LSI) 173 174 181
Linearly independent 284
Literal 314
Little, J.D.C. 439 452
Live node 437
Local optimum 8—10 455
Local search 401 454—81
Local search, variable-depth 468
Lovasz, L. 192 306
Lower bound 438
Lower bound on the flow 135 215
lp see “Linear program linear
LSI see “Linear strict inequalities”
Lueker, G. 382
Maheshwari, S.N. 217
Malhotra, V.M. 217
Markov, A.A. 190
Master problem 99
Matched edge 219
Matched node 219
Matching 218
Matching matroid 303
Matching problem 2 218
Matching problem, bipartite 221—26 248—55
Matching problem, bottleneck 245
Matching problem, nonbipartite 226—43 255—66 269
Matching problem, weighted 247—66 282
Matching, b- 245 268
Matching, complete (or perfect) 219 267
Matching, maximum 219
Matching, proper 258
Matric matroid 288 304
Matrix, distance 4—5 410—11
Matrix, incidence 318
Matrix, totally unmodular 249 316—18
Matrix, Tutte 243
Matrix, unimodular 316
Matroid 271 280—301
Matroid intersection problem 289—98 300
Matroid intersection problem, weighted 298—99
Matroid parity problem 299
Matroid partition problem 305
Matroid, dual 305
Matroid, graphic 287
Matroid, head-partition 288
Matroid, matching 303
Matroid, matric 288 304
Matroid, tail-partition 288
Matroid, transversal 303
MAX-CUT 379 403
Max-flow problem (or MFP) 91—97 114—15 117—28 200—214 225
Max-flow, min-cut Theorem 117—20 203
Maximal flow 206
Maximum (or max) flow 91
Maximum matching 219
Maximum weight forest problem (or MWF) 278—80
Maxwell, W.L. 445 453
McCormick, G.P. 17
MCSN see “Minimum-cost survivable network”
Median algorithm 301 477
Metric 411
MFP see “Max-flow problem”
Micali, S. 246
Miller, C.E. 324
Miller, L.W. 445 453
MILP see “Mixed integer linear programming”
Min-cost flow problem 137—51
Min-cost flow problem, multicommodity 151
Minimal spanning tree problem (or MST) 5 6 7 158 271—80 301—2 303 442 443
Minimum cover 391
Minimum-cost survivable network problem (or MCSN) 456—62
Minty, G.J. 134 136 190
MIXED CHINESE POSTMAN 379
Mixed integer linear programming (or MILP) 310 313 324 438
Moment problem 16
Moore, E.F. 453
MST see “Minimal spanning tree problem”
Multicommodity flow 152 379
Multigraph 20
Multigraph, Eulerian 412
Multiprocessor scheduling 363—66 393 402 431
Mulvey, J.V. 154
Murty, K.G. 452
MWF see “Maximum weight forest problem”
n-dimensional tic-tac-toc 187
Naamad, A. 217
Neighborhood 7—8 454
Neighborhood,  -change 463
Neighborhood, 2-change 7—8 455
Neighborhood, exact 10 62—63 471—81
Neighborhood, k-change 7—8 455
Neighborhood, swap 466—67
Neighborhood, X-change 460
Nemhauser, G.L. 135 341
Nemirovskii, A.S. 191
Network 23
Network, auxiliary 205
Network, incremental 139
Network, layered 205 448
network, simple 213 225 458
Network, with unit arc capacities 212—14 225
Ninamiya, K. 246
Node (in branch-and-bound) 436
Node (in branch-and-bound), dead 436
Node (in branch-and-bound), live 437
Node (or vertex) 20
Node (or vertex), exposed 219
Node (or vertex), inner 219 260
Node (or vertex), matched 219
Node (or vertex), outer 219 260
Node (or vertex), pseudo- 260
Node cover 361 363 406—09
Nonbasic gradient pivoting rule 50—51
Nondeterministic Turing machine 398
Nonlinear programming problem 1
Nonlinearity 312
Norman, R.Z. 246
North, J.H. 484
NOT 314
NP 349
|
|
|
| Реклама |
|
|
|
|
|
О проекте