|
|
Авторизация |
|
|
Поиск по указателям |
|
|
|
|
|
|
|
|
|
|
Grotschel M., Lovasz L., Schrijver A. — Geometric Algorithms and Combinatorial Optimization |
|
|
Предметный указатель |
Eulerian trail 19
Even circuit 19
Even cycle 236
Even, S. 255 280 335
Expansion parameter 82
Extended polymatroid 306 306—324 316
Extremal ray 184
Face 9
Facet 9
Facet-complexity 163 163—165
Faddeev, D.K. 1 335
Faddeeva, V.N. 1
Family, crossing 315 315—324
Family, intersecting 315 315—324
Family, lattice 313 313—319 325—329
Family, ring 313 313—319 325—329
Farkas lemma 12
Farkas, Gy. 15
Feasible solution 15
Feedback arc set 253 253—254
Feinstein, A. 199 335
Fenchel, W. 49 332
Feofiloff, P. 252 335
FLOOR 2
Flow 197 197—201 233—242
Flow value 197
Flow, minimum-cost 238—242
Flow, multicommodity 266—271
Flow, multiterminal 249
Flow-equivalent 249
Floyd, R.W. 235 335
Fonlupt, J. 250 274 281 332 335
Ford, L.R., Jr. 197 198 199 202 231 234 237 239 279 280 335
Forest 20
Forest polytope 216 216—217
Frank, A. vii 168 189 190 216 247 252 280 324 335
Fridman, A.A. 336
Frobenius norm 8
Frobenius' marriage theorem 204
Frobenius, E G. 203 204 230 335
Frumkin, M.A. 45 155 336
Fueredi, Z. 127 331
Fulkerson's optimum arborescence theorem 243
Fulkerson, D.R. 197 198 199 202 225 231 234 237 238 239 241 243 246 277 279 280 284 335 336
Full column rank 3
Full row rank 3
Full-dimensional 3
Fully polynomial approximation algorithm (scheme) 35
Function minimization, odd submodular 325—329
Function minimization, submodular 310 310—311 315 316 325—329
Function, convex 49 55—56 188
Function, submodular 304 304—308
Function, support 49
Gabow, H.N. 243 247 336
Gain, maximum 241
Galil, Z. 231 236 243 247 336
Gallai graph 281
Gallai, T. 230 231 255 280 281 336
Gamma-function 68
Gantmacher, F.R. 1
Garey, M.R. 21 28 219 272 336
Gass, S.I. 1 337
Gathen, J. yon zur 45 155 337
Gaussian elimination 36—40
Gavril, F. 280 337
General Euclidean norm 5
Geometry of numbers 138—156
Gerards, A.M.H. 274 275 337
Gershovich, V.I. 94 345
Gewirtz, A. 332
Ghellinck, G. de 66 337
Ghouila-Houri, A. 280 337
Giles, R. 16 244 302 316 319 320 321 322 334 337 344
Gill, P.E. 66 337
Gilmore, P.C. 280 337
Glover, F. 236 337
Goffin, J.-L. 65 122 337
Goldberg, A.V. 237 337
Goldfarb, D. 65 71 72 82 94 107 248 332
Golumbic, M. 283 337
Gomory, R.E. 13 233 248 249 257 331 337
Gomory-Hu tree 249
Graham, R.L. 221 248 337
Gram — Schmidt orthogonalization 40
Graph 16—18 17
Greedy algorithm 212 212—213 246 306—308
Greenberg, H. 332
Greene, C. 250 337
Gritzmann, P. 66 332
Groetschel, M. 65 107 159 193 218 223 249 250 254 263 265 283 285 326 331 337 338 341 343
Gross, O.A. 280 336
Gruenbaum, B. 1 69 333 338
Guy, R. 334 344
H-perfect graph 299
Hadamard inequality 8
Hadlock, F. 250 338
Hajnal, A. 280 335 338
Half-integer multicommodity flow problem 267
Halfspace 9
Hall, M., Jr. 231 337 338
Hamiitonian graph 19
Hamiltonian circuit 19
Hamiltonian circuit problem 21
Hamiltonian digraph 19
Hamiltonian tour 19
Hanani, H. 334 344
Handle 264
Hartvigsen, D.B. 265 338
Hassin, R. 324 338
Hayward, R.B. 282 338
head 18
Hell, P. 248 337
Heller, I. 282 338
Hellman, M.E. 221 331
Hensel, K. 338
Hermite normal form 43 43—45 155 155—156
Hermite, C. i 43 140 338
Hoang, C.T. 281 333
Hoffman, A.J. 199 238 239 241 280 282 337 339
Holland, O. 223 338
Holyer, I. 208 209 339
Homogenization, 1- 185
Hopcroft, J.E. 21 231 274 339
Hsu, W.-L. 282 302 339
Hu, T.C. 248 249 257 268 337 339
Hull, affine 3 182—184
Hull, conic 3
Hull, convex 3
Hull, linear 3
Hypergraph 225
Hyperplane 9
Ibarra, O.H. 35 339
Ideal in a partially ordered set 314
Identity matrix 2
Ikura, Y. 302 339
Imai, H. 66 339
Incidence vector 1
incident 17
Incident from 18
Incident to 18
Indegree 18
Independence testing, linear 40
Independent set of a matroid 211
Induced graph 17
Inequalities problem, linear diophantine 11—14 192 192—196
Inequalities, linear 9—13 41—43 49 75 189—191
Inequality system 9—11 75
Ingleton, A.W. 304 339
Initial endnode 18
Inner product 2
| Inner radius 53
Input of a problem 22
Input size 23 30
Instance of a problem 21 22
Integer linear programming 15—16 192—196
Integer linear programming problem 16
Integer multicommodity flow problem 267
Integral optimization over extended polymatroids 309
Integral polyhedron 200
Interior -ball of K 6
Internal node 19
Intersecting family 315 315—324
Intersection of convex sets 129—131 188
Intersection of two matroids 214 214—218 306 310
Interval graph 279
Inverse matrix 40
Iri, M. 66 211 339
Isolated node 17
Isthmus 19
Jensen, P.M. 309 339
John, F. 69 124 339
Johnson, D.S. 21 28 219 267 272 336 339
Johnson, E.L. 257 258 260 261 262 334
Join, T- 259 259—262
Jordan, W. 124
Juenger, M. vii 250 254 331 338
K-connected graph 19
Kannan, R. 45 151 334 339
Kariv, O. 255 335
Karmarkar's method 65—66
Karmarkar, N. 65 66 339
Karp, R.M. vii 28 65 189 231 238 239 249 265 334 339 340
Karzanov, A.V. 252
Khachiyan, L.G. v 25 64 65 71 157 158 180 181 198 232 235 242 265 340
Khintchine, A. 132 136 340
Kim, C.E. 35 339
Klee, V. 42 64 69 333 340
Klingman, D. 236 337
Knuth, D.E. 250 340
Koenig's edge coloring theorem 209
Koenig's edge covering theorem 230
Koenig's matching theorem 230
Koenig, D. 25 209 210 230 231 232 238 240 277 279 280 305 332 340
Konnerth, T. vii
Koopmans, T.C. 232 333
Korte, B. 309 337 339 341 344
Kozlov, M.K. 181 340
Kronecker, L. 334
Kruskal, J.B. 199 247 282 339 340
Kuhn, H.W. 233 279 280 339 340
Kupferschmid, M. 64 334
Kuratowski, C. 25
Kwan, M.-K. 262 340
Lagarias, J.C. 138 218 220 221 340 341
Laminar 317
Lancaster, P. 1 341
Las Vergnas, M. 282 332
Lattice 139 139—156
Lattice family 313 313—319 325—329
Lattice vector problem, nearest 141
Lattice vector problem, shortest 140 143
Lawlet, E.L. 16 65 216 324 338 341 343
Leading principal submatrix 2
Lehman, A. 225 226 227 228 246 252 284 341
Lekkerkerker, C.G. 139 280 341
Lempel, A. 280 335
Length 19 23
Lenstra, A.K. 133 141 149 341
Lenstra, H.W., Jr. v vi 124 133 134 141 149 162 193 195 196 341
Lenstra, J.K. 338 343
Levin, A.Yu. 65 341
Levin, L.A. 65 104 346
Line graph 18 279 302
Line perfect graph 281
Lineality space 10 183
linear combination 3
Linear diophantine equations 11—12 45 155—156
Linear diophantine inequalities problem 11—14 192 192—196
Linear equations 11—12 36—40
Linear form problem, small 139 147
Linear hull 3
Linear independence testing 40
Linear inequalities 9 43 41—43 49 75 189—191
Linear program 14
Linear programming 14—16 41—43 49 180 188 192
Linear programming duality 15
Linear programming problem 14
Linear programming, integer 15—16 192—196
Linear subspace 3
Linearly (in)dependent 3
Liu, T H. 201 242 333
Loewner, K. 69
Loewner-John ellipsoid 69 69—73 122—127
Lomonossov, M.V. 268 341
Longest branching problem 245
Longest dipath problem 240
Lovasz, L. 65 107 133 140 141 149 159 160 181 193 195 218 230 246 259 261 262 275 277 283 285 309 311 326 334 337 338 341 342 344
Lower integer part 2
LP-relaxation 16
Lucchesi, C.L. 251 252 253 254 321 342
Lucchesi—Younger theorem 252
Lueker, G.S. 280 281 332 342 344
Mader, W. 225 247 342
Magnanti, T.L. 250 337
Mahadev, N.V.R. 281 333
Mahjoub, A.R. 249 250 254 331 335
Marcus, M. 1 342
Marsh, A.B., III. 256 257 258 333 342
Martel, C.U. 324 341
Matching 17 203—208 229 229—233 253—254 305
Matching number 229
Matching polytope 204—206 255 255—256
Matching polytope, b- 257
Matching problem 255
Matching, 1- 17
Matching, b- 46 257 257—259 265
Matrix 2
Matrix norm 7 7—8
Matroid 210—218 211 305—306 311—313
Matroid intersection 214 214—218 306 310
Matroid polytope 213 213—218
Maurras, J.F. 282 342
Max-flow min-cut property 226 226—229 252
Max-flow min-cut theorem 199 237
Max-potential min-work theorem 234
Maximum (r, s)-cut problem 239
Maximum (r, s)-dicut problem 239
Maximum (r, s)-flow problem 197 236
Maximum cut problem 249
Maximum degree 230
Maximum degree problem 209
Maximum flow problem 197 236
Maximum norm 5
Maximum potential problem 234
Maximum-gain flow problem 241
Megiddo, N. 189 342
Membership oracle 54
Membership problem, strong 48 48—50 170—174
Membership problem, weak 51 51—55 56—58 61—63 102—122 128—132 170—174
Menger's Theorem 238
Menger, K. 25 238 342
Merkle, R.C. 221 331
Mertens, F. 149 343
Meyniel graph 281
Meyniel, H. 281 282 283 342
Micali, S. 255 342
Miller, R.E. 340
Min-potential max-work theorem 240
Minc, H. 1 342
Minimal face 183
|
|
|
Реклама |
|
|
|